\documentclass{xmgr}
\usepackage[noenc]{tipa}
\usepackage{tipx}
\usepackage[geometry,weather,misc,clock]{ifsym}
\usepackage{pifont}
\usepackage{eurosym}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amssymb,amsfonts,textcomp}
\usepackage{array}
\usepackage{supertabular}
\usepackage{hhline}
\usepackage{graphicx}

%\defaultfontfeatures{Scale=MatchLowercase}
%\setmainfont[Numbers=OldStyle,Ligatures=TeX]{Minion Pro}
%\setsansfont[Numbers=OldStyle,Ligatures=TeX]{Myriad Pro}
% for fontspec version < 2.0
\setmainfont[Numbers=OldStyle,Mapping=tex-text]{Minion Pro}
\setsansfont[Numbers=OldStyle,Mapping=tex-text]{Myriad Pro}
%\setmonofont[Scale=0.75]{Monaco}
\setcounter{secnumdepth}{3}
% Opcjonalnie identyfikator dokumentu 
% drukowany tylko z włączoną opcją 'brudnopis':
\wersja   {wersja wstępna [\ymdtoday]}
\newcounter{Drawing}
\newcounter{Tabela}
\newcounter{Wykres}
\author   {Bartłomiej Kossakowski}
\nralbumu {164\,653}
\email    {kossakowski.b@gmail.com}



\title    {Gene Expression Programming ~wraz z biblioteką programów}
\date     {styczeń 2012}
\miejsce  {Gdańsk}

\opiekun  {prof. UG dr hab. Joanna Jędrzejowicz}

% dodatkowe polecenia
%\renewcommand{\filename}[1]{\texttt{#1}}
\begin{document}
\bibliographystyle{plain}
\maketitle %spis tresci i tytul

\chapter{Wstęp}
\ Nie będzie przesadą stwierdzenie, że inspiracje zjawiskami przyrodniczymi przy rozwiązywaniu problemów człowieka pojawiały się już u pierwszych przedstawicieli naszego gatunku. Od imitujących pazury dzikich zwierząt ostrzy używanych przez myśliwych, przez obserwacje lotu ptaków, by samemu wzbić się w powietrze, do czasów nam współczesnych, wciąż spoglądamy na techniki wykorzystywane przez naturę.
Zdaje się więc, że kwestią czasu było zainteresowanie się mechanizmami biologicznymi przez
informatyków. Nie inaczej narodziły się idee stworzenia sztucznej inteligencji czy {\quotedblbase}sztucznego życia'' w oparciu o programy komputerowe. Same algorytmy będące próbą połączenia teorii ewolucji z informatyką, są tworem stosunkowo młodym, badania nad nimi sięgają lat pięćdziesiątych dwudziestego wieku, przełom zaś nastąpił w połowie lat sześćdziesiątych. 


Jak przeczytać można w \cite{Wierzchon}, podstawowymi uwarunkowaniami ewolucji są dobór naturalny (selekcja) oraz rozmnażanie płciowe (zapewnienie różnorodności), w uproszczeniu zaś proces można określić jako {\quotedblbase}walka o przetrwanie najlepiej przystosowanych'' osobników. Czytając dalej, należy zaznaczyć, że w darwinowskiej teorii ewolucji zachodzące zmiany mają na celu odnajdowanie ulepszeń, nie zaś rozwiązania optymalnego.


\textit{Algorytm genetyczny} stanowi rozszerzenie idei algorytmu ewolucyjnego poprzez uogólnienie go do tego stopnia, by był w stanie reprezentować strukturę każdego problemu (\cite{Wierzchon}). W każdym jednak przypadku, działanie opiera się na trzech podstawowych krokach:


\begin{itemize}
\item 
stworzeniu populacji początkowej
\item 
ocenie jakości osobników
\item 
stworzenie kolejnej populacji poprzez operacje genetyczne na osobnikach.
\end{itemize}

Osobniki populacji nazywane są \textit{chromosomami}, składają się one z szeregu \textit{genów}, które zaś przyjmować mogą skończoną liczbę wartości, nazywanych \textit{allelami}. Zespół genów, składających się na osobnika nazywamy \textit{genotypem}, zaś jego produkt, rozumiany jako zbiór cech organizmu powstały z interakcji genotypu ze środowiskiem, nazywany jest \textit{fenotypem}.


W przypadku, gdy osobnik reprezentuje spójny program komputerowy, mechanizm ten nazywany jest \textit{programowaniem genetycznym}. 


Ciekawe i nowatorskie podejście do algorytmów ewolucyjnych, Gene Expression Programming -- Programowanie Ekspresji Genu, zaprezentowane zostało przez dr C\^andidę Ferreirę po raz pierwszy w pracy \cite{Ferreira.mmbaa}. Ta właśnie technika, wraz z przykładem implementacji oraz przykładami zastosowania, jest przedmiotem tej pracy.

%% 1.1
\section{Ekspresja genu}
{\quotedblbase}Gene expression'' - czyli ekspresja genu - jest jednym z podstawowych procesów w makromolekularnych mechanizmach życiowych. W uproszczeniu, polega on na odczytaniu informacji zawartych w genie i przepisaniu ich na białka lub formy kwasów rybonukleinowych (RNA), stanowiące produkty procesu. Wykorzystywany jest przez wszystkie znane formy życia, zarówno eukarionty (organizmy zbudowane z komórek posiadających jądro komórkowe i chromosomy), prokarionty (mikroorganizmy niezawierające jądra komórkowego, np
bakterie), jak i prawdopodobnie wirusy. Proces ten ilustruje rysunek 1.\footnote{The Medical News,
http://www.news-medical.net/health/What-is-Gene-Expression.aspx, tłumaczenie własne}

Proces przebiega etapowo\footnote{W opisie pominięto etapy o niewielkiej istotności z punktu widzenia informatyki,
takie jak transport czy degradacja RNA i białek \ }:

\begin{center}
\begin{minipage}{9.636cm}
{\itshape
Rysunek \stepcounter{Drawing}{\theDrawing}: Struktura oraz ekspresja genu}
\includegraphics[width=9.636cm,height=10.061cm]{"praca-img001.jpg"}\end{minipage}
\end{center}


\begin{itemize}
\item 
transkrypcja, czyli przepisywanie informacji zawartej w DNA na RNA, w wyniku której powstaje pre-mRNA (RNA
zawierający sekwencje niekodujące, tzw introny, oraz części kodujące, tzw egzony)
\item 
obróbka post-transkrypcyjna, w wyniku której powstaje mRNA (RNA przenoszący informacje)
\item 
translacja białka, czyli ostateczne formowanie białka na podstawie informacji zawartych w kodzie genetycznym. 


\bigskip
\end{itemize}

Sekwencja mogąca ulec translacji w białko nazywana jest \textit{otwartą ramką odczytu }(ORF -- ang. Open Reading Frame). Pojęcie to jednak w kontekście GEP ma nieco inne znaczenie, które zostanie opisane poniżej.

%% 1.2
\section{GEP a algorytmy genetyczne i programowanie genetyczne}

\ Idea przyświecająca algorytmom ewolucyjnym polega na przeszukiwaniu przestrzeni rozwiązań w celu znalezienia najlepszego z nich. W tym celu wprowadza się pewną losowo wygenerowaną populację, na której wykonywane są operacje genetyczne. Populacja składa się z chromosomów, w których zakodowane są informacje. Z każdą iteracją pętli algorytmu, z puli {\quotedblbase}kandydatów na rozwiązania'' - z pomocą funkcji przystosowania, oceniającej jakość fenotypu (rozwiązania przedstawianego przez chromosom) - wybierane są osobniki najlepiej rokujące, będące następnie {\quotedblbase}rodzicami'' kolejnej populacji. 


GEP łączy elementy dwóch podstawowych podejść do obliczeń ewolucyjnych, mianowicie algorytmy genetyczne(GA - ang. \textit{genetic algorithms}) oraz programowanie genetyczne (GP - ang. \textit{genetic programming}). 


W algorytmach genetycznych w tradycyjnej formie, istotnym problemem implementacji jest kwestia kodowania informacji w chromosomie. Najczęściej spotykanym (niejako kanonicznym) podejściem jest użycie chromosomów w postaci wektorów zero-jedynkowych o jednakiej długości, w których genem nazywamy pojedynczy bit, choć nie jest to regułą. Operacje genetyczne są wtenczas wykonywane bezpośrednio na ciągu znaków, nie zachodzi potrzeba kontroli osobnika pod kontem spójności. Przykład operacji mutacji na typowym dla GA chromosomie przedstawiony jest poniżej 


$\textsf{0100}\textbf{1}\textsf{101} \ \longrightarrow \  \textsf{0100}\textbf{0}\textsf{101}$


Programowanie genetyczne z kolei, za swój cel stawia znalezienie \textit{programu} rozwiązującego problem.
Różnica względem klasycznego GA polega na formie chromosomów. Z racji specyfiki rozpatrywanych problemów,
osobniki populacji reprezentują drzewo składni. Przechowywanie osobnika jest kwestią implementacji, jednak
najpopularniejszym podejściem jest rzutowanie drzewa na ciąg operacji w notacji quasi-prefiksowej. Długość
chromosomu oraz rodzaj elementów go tworzących nie jest więc z góry ustalona. Operacje genetyczne są w
tym przypadku przeprowadzane na drzewie, które podatne jest na utratę spójności przy ingerowaniu
bezpośrednio w ciąg znaków. Konieczne jest więc zagwarantowanie, że np. krzyżowane będą jedynie
poddrzewa (przykład krzyżowania poddrzew przedstawiony jest na rysunku 2.). 

\begin{center}
\begin{minipage}{9.419cm}
{\itshape
Rysunek \stepcounter{Drawing}{\theDrawing}: Przykład krzyżowania poddrzew stosowanego w programowaniu genetycznym.
\includegraphics{"praca-img002.png"}
}


\end{minipage}
\end{center}
Opisywane w niniejszej pracy podejście łączy zalety GA i GP. Populacja składa się z ciągów
znaków jednakowej długości, jednak reprezentujących drzewo parsowania. Operacje genetyczne dokonują
się na wektorze \textit{przed} zinterpretowaniem go jako drzewo. Pozwala to zapobiec wystąpieniu
{\quotedblbase}błędnych protein''. 


\chapter[Opis algorytmu]{\selectlanguage{polish} Opis algorytmu}
\begin{center}
\begin{minipage}{8.557cm}
{\centering\itshape
Rysunek \stepcounter{Drawing}{\theDrawing}: Schemat blokowy algorytmu GEP
\par}
\includegraphics[width=8.557cm,height=12.136cm]{"praca-img003.jpg"}\end{minipage}
\end{center}

W rozdziale tym przedstawiony i omówiony zostanie algorytm GEP, jego przebieg oraz szczegóły struktur jego
podstawowych {\quotedblbase}aktorów''. Prezentuje on również metodę, którą realizowana jest ekspresja
genów nim używanych.



\section[Przebieg algorytmu]{Przebieg algorytmu}

Przebieg algorytmu przedstawia schemat na 3. Na jego początku, po wygenerowaniu losowej populacji początkowej,
każdy z chromosomów tłumaczony jest na drzewo składni, reprezentujące wyrażenie. Każdy z nich oceniany
jest przez funkcję przystosowania. Następnie, jeśli osiągnięty został wynik satysfakcjonujący
lub wykonana została określona uprzednio liczba iteracji, algorytm kończy działanie, jako wynik podając
najlepsze dostępne rozwiązanie. W przeciwnym wypadku dokonywana jest replikacja najlepszych osobników, oraz
poddanie ich operacjom genetycznym, mającym na celu wprowadzić większą różnorodność
genetyczną. Te chromosomy stanowią kolejną populację, a algorytm wraca do punktu ekspresji genów.
Złożoność obliczeniowa jest więc szacowana przez  $O(g\cdot f)$ (\textit{g} -- liczba generacji w jednym
przebiegu, \textit{f --} liczba danych uczących). Szczegóły poszczególnych etapów przedstawione zostaną w dalszej części pracy.

\section[Otwarta ramka odczytu a gen]{ Otwarta ramka odczytu a gen}

Jak zostało wspomniane, w genetyce funkcjonuje pojęcie Open Reading Frame, oznaczające fragment genu
rozpoczynający się kodonem startu, a kończący kodonem stopu. Pomiędzy nimi znajdują się
informacje. To właśnie szukając ORFów odnajduje się pojedyncze geny. 


GEP odbiega odrobinę od takiego schematu. Podobnie, oprócz ORF w chromosomie mogą istnieć fragmenty
niekodujące, jednak nie mamy do czynienia z kodonami początku i końca sekwencji. ORF zawsze zaczyna się
bowiem na pierwszej pozycji, kończy zaś gdy drzewo wyrażenia jest kompletne. 


Niech za przykład posłuży następujący ciąg znaków:


\bigskip

{\selectlanguage{polish}
\ \ \texttt{012345678}}

{\selectlanguage{polish}
\ \ \texttt{+++aba*ab}}


\bigskip

Traktując ten ciąg jako quasi-prefiksowy zapis wyrażenia algebraicznego, otrzymujemy drzewo:

\begin{center}
\includegraphics[width=7.964cm,height=5.212cm]{praca-img004.png}
\end{center}
{\selectlanguage{polish}
czyli wyrażenie $(a+b)+(a+(a \cdot b))$}


Traktując ten ciąg jako quasi-prefiksowy zapis wyrażenia algebraicznego, otrzymujemy drzewo:

\begin{center}
\includegraphics[width=7.964cm,height=5.212cm]{praca-img004.png}
\end{center}
{\selectlanguage{polish}
czyli wyrażenie $(a+b)+(a+(a\cdot b))$}


\bigskip

{\selectlanguage{polish}
\ Rozumując w drugą stronę: każde wyrażenie (czy to algebraiczne, czy logiczne) da się przedstawić w
postaci drzewa. Zczytując symbole od góry do dołu oraz od lewej do prawej, otrzymujemy ORF kodujący dane
wyrażenie.}

{\selectlanguage{polish}
\ \ Cechą, która wyróżnia GEP na tle klasycznych algorytmów ewolucyjnych, jest struktura genów. Każdy
gen składa się z tzw \textit{głowy} oraz \textit{ogona}. W części pierwszej znajdować się
mogą zarówno symbole funkcyjne (należące do zbioru F), oraz symbole terminalne (należące do zbioru
T), w \textit{ogonie} zaś jedynie terminale. Długość \textit{głowy} \textit{h }ustalana jest odgórnie, w
zależności od problemu, długość \textit{ogona} \textit{t }natomiast jest funkcją od \textit{h }i
wyraża się równaniem:}


\bigskip

$t = h(n-1)+1$


\bigskip

{\selectlanguage{polish}
gdzie \textit{n }\ jest maksymalną arnością spośród operatorów funkcyjnych. Dla przykładu, niech
\textit{F=\{+,-,*,/\}, T=\{a,b\}, h=4. }Wszystkie operatory arytmetyczne są dwuargumentowe, wobec tego
\textit{n=2}. Długość ogona wynosi więc \textit{t}=\textit{4(1)+1=5. }}

{\selectlanguage{polish}
Podejście takie pozwala zapobiec powstawaniu drzew, dla których {\quotedblbase}nie starcza'' terminali.
Niezależnie bowiem od kierunku, w jaki pójdzie mutacja (bąd\'z losowa inicjacja pierwszej populacji), ORF
może stanowić zarówno cały gen (w przypadku, kiedy cała \textit{głowa} składa się z symboli
funkcyjnych), bąd\'z też być jednoelementowa (druga skrajność: pierwszy element \textit{głowy} jest
symbolem terminalnym).}


\bigskip

\section[Chromosomy wielogenowe]{\selectlanguage{polish} Chromosomy wielogenowe}
{\selectlanguage{polish}
\ \ Jakkolwiek poprawnym jest używanie w algorytmie osobników będącycg pojedynczym genem, lepsze wyniki
można najczęściej osiągnąć stosując chromosomy wielogenowe. Pozwala to lepiej wykorzystać
zalety wynikające z manipulacji na ciągu znaków przed sparsowaniem go na program. Liczba genów na
chromosom, podobnie jak długość \textit{głowy, }obierane są z góry dla danego problemu, bąd\'z
przebiegu algorytmu. Jako że każdy z genów traktowany jest jako poddrzewo całego drzewa powstałego z
chromosomu, konieczne jest również wybranie funkcji spajającej poddrzewa w całość. Dla przykładu,
niech chromosom składa się z dwóch poddrzew, \textit{h=4, t=5, F=\{+,-,*,/\}, T=\{a\},} funkcją
spajającą niech będzie operacja dodawania. Tu, jak i w dalszej części, korzeń drzewa
odpowiadający za funkcję łączącą, oznaczony jest czerwoną obwódką. (Pionową
kreską rozdzielone graficznie zostały poszczególne geny, jednak jedynie w celach poglądowych, w
części operacji genetycznych chromosom jest bowiem traktowany jako jeden spójny ciąg znaków.)}


\bigskip


\ \ \texttt{012345678{\textbar}012345678}

\ \ \texttt{++a/aaaaa{\textbar}-a-*aaaaa}


\bigskip


\bigskip



\begin{center}
\includegraphics[width=9.181cm,height=6.641cm]{praca-img005.png}
\end{center}

\bigskip


W tym miejscu warto porównać GEP do bardziej tradycyjnych metod GP. W tych drugich operacje genetyczne wykonywane
są na strukturze grafowej, tu -- na ciągu znaków. Sprawia to, że z pozoru niewielka zmiana (np. mutacja
jednego elementu) może spowodować znaczące zmiany w strukturze drzewa wynikowego.


\bigskip

\section[Selekcja i replikacja]{\selectlanguage{polish} Selekcja i replikacja}
{\selectlanguage{polish}
\ \ Jedną z najważniejszych kwestii przy projektowaniu algorytmu ewolucyjnego jest wybór metody selekcji
osobników do replikacji i utworzenia kolejnej generacji. W ogólności proces ten polega na wyborze osobników,
które w danym momencie dają najlepsze wyniki, bąd\'z są najlepiej rokujące, oraz ich skopiowaniu do
następnej populacji, by w dalszej kolejności poddać je operacjom genetycznym.}

{\selectlanguage{polish}
\ Do oceny {\quotedblbase}jakości'' osobnika służy \textit{funkcja przystosowania} (ang. \textit{fitness
function}). Jej ustalenie jest zależne od specyfiki problemu. Zazwyczaj jej wartość przyrównywana jest do
maksymalnej (bąd\'z minimalnej) wartości idealnej. Kolejne iteracje algorytmu mają w efekcie prowadzić do
podnoszenia (bąd\'z obniżania) wartości \textit{fitness}, tak by zbliżyć ją najbardziej jak to
możliwe do wartości idealnej. Aby tego dokonać, rozpatrywany fenotyp przeciwstawiany jest szeregowi
\textit{danych uczących }(również \textit{danych treningowych} bąd\'z z ang. \textit{fitness cases}), czyli
danym mającym zweryfikować jego skuteczność. }

{\selectlanguage{polish}
Istnieje co najmniej parę metod selekcji osobników, m. in. deterministyczna metoda rankingowa, czy metoda
turniejowa, losująca pewną liczbę osobników podzielonych na grupy, następnie zostawiająca te
względnie najlepsze spośród wybranych. Autorka systemu wybrała selekcję proporcjonalną zwaną
metodą koła ruletki (ang. roulettewheel). Polega ona na przypisaniu fenotypów do pól wyimaginowanego koła
ruletki. Wielkość pola jest wprost propocjonalna do wartości dostosowania osobnika. Następnie zachodzi
losowanie (analogia do zakręcenia kołem ruletki), przy czym im większa wartość funkcji przystosowania,
tym większe prawdopodobieństwo wyboru osobnika. Pseudokod algorytmu losowania przedstawiony jest poniżej}

{\selectlanguage{polish}
\ \ \texttt{begin}}

{\selectlanguage{polish}\ttfamily
\ \ \ \ r := random;}

{\selectlanguage{polish}\ttfamily
\ \ \ \ s := 0.0;}

{\selectlanguage{polish}\ttfamily
\ \ \ \ i := 0;}

{\selectlanguage{polish}\ttfamily
\ \ \ \ repeat}

{\selectlanguage{polish}\ttfamily
\ \ \ \ \ \ i := i+1;}

{\selectlanguage{polish}\ttfamily
\ \ \ \ \ \ s := s + ps[i]}

{\selectlanguage{polish}\ttfamily
\ \ \ \ until s {\textgreater}= r;}

{\selectlanguage{polish}\ttfamily
\ \ \ \ return(i);}

{\selectlanguage{polish}\ttfamily
\ \ end}


\bigskip

{\selectlanguage{polish}
Na początku losowana jest liczba z zakresu 0-100. Następnie dodawane są procentowe wartości dostosowania
kolejnych osobników, dopóki suma nie przekroczy wylosowanej liczby. Jak widać, im większa liczba, tym
większe prawdopodobieństwo zwrócenia osobnika o wysokiej wartości przystosowania. }


\bigskip

{\selectlanguage{polish}
W porównaniu z innymi metodami selekcji, selekcja ruletkowa może dawać gorsze rezultaty (patrząc pod kontem
faktycznej selekcji najlepszych osobników, przy jednoczesnym zachowaniu różnorodności genetycznej poprzez
pozwolenie na replikację osobników słabszych), jednak przy wprowadzeniu {\quotedblbase}prostego elityzmu''
(ang. \textit{simple elitism}), polegającego na zachowaniu i replikacji bezwzględnie najlepszego osobnika,
większość powszechnie stosowanych metod selekcji wykazuje podobne rezultaty, ze wskazaniem na koło ruletki
przy bardziej skomplikowanych problemach (\cite{Ferreira.gepips}).}


\bigskip


\bigskip

\section[Modyfikacja]{\selectlanguage{polish} Modyfikacja}
{\selectlanguage{polish}\bfseries
\ \ \textmd{Istotą algorytmów ewolucyjnych są wprowadzające element losowy modyfikacje populacji. W
założeniach GEP, z wyjątkiem mutacji, żaden operator nie może modyfikować chromosomu więcej niż
raz. Z drugiej strony, jeden chromosom może być modyfikowany przez więcej niż jeden }\textmd{operator,
bąd\'z też nie być zmieniany ani razu. Wszystkie procesy przebiegają losowo: zarówno w kwestii wyboru
chromosomu, jak i sposobu przebiegu operacji. }}

{\selectlanguage{polish}\bfseries
\textmd{Wszystkie modyfikacje podlegają pewnym parametrom, dla przykładu, dla wska\'znika transpozycji (ang.
}\textmd{\textit{transposition rate}}\textmd{) równemu 0.7, siedem na dziesięć osobników zostanie wybranych
do transpozycji.}}

\subsection[Mutacja]{\selectlanguage{polish} Mutacja}
{\selectlanguage{polish}\bfseries
\textmd{Jest to najbardziej podstawowa forma modyfikacji. Polega na zamienieniu elementu na inny. Najpierw losowo
wybierany jest chromosom, następnie, również losowo, element do mutacji, oraz element finalny. Jest to jedyny
moment, w którym zagwarantować należy spójność danych, bo, chociaż mutacja może zajść w każdym
miejscu, niemożliwe jest zmutowanie terminala z }\textmd{\textit{ogona }}\textmd{w operator funkcyjny (w drugą
stronę taka zamiana nie stanowi problemu). Zazwyczaj stosuje się dwie mutacje na jeden gen (mutowanie jednego
jedynie symbolu w chromosomie mogłoby skutkować niewystarczającą zmianą różnorodności
genetycznej).}}

{\selectlanguage{polish}\bfseries
\textmd{Przykładowo niech }\textmd{\textit{h=4, }}\textmd{wybrane do mutacji symbole na pozycjach 0 i 11 mutują
}\textmd{odpowiednio na }\textmd{\textit{a}}\textmd{ }\textmd{i }\textmd{\textit{Q}}\textmd{ (oznaczający
pierwiastek kwadratowy)}}


\bigskip

{\selectlanguage{polish}\bfseries
\ \texttt{\textmd{012345678{\textbar}012345678 \ \ \ \ \ 012345678{\textbar}012345678}}}

{\selectlanguage{polish}\bfseries
\ \texttt{\textmd{+}}\texttt{\textmd{{}-*aaabaa{\textbar}*}}\texttt{\textmd{*}}\texttt{\textmd{/+bbaab
\ {}-{\textgreater}
\ }}\texttt{\textmd{a}}\texttt{\textmd{{}-*a}}\texttt{\textmd{a}}\texttt{\textmd{abba{\textbar}*}}\texttt{\textmd{Q}}\texttt{\textmd{/+bbaab}}}


\bigskip


\bigskip



\begin{left}
\includegraphics[width=7.779cm,height=5.563cm]{praca-img006.png}
\end{left}
\begin{right}
\includegraphics[width=6.1cm,height=5.061cm]{praca-img007.png}
\end{right}

\bigskip


\bigskip

{\selectlanguage{polish}
Jak widać, mimo że zmiany nastąpiły tylko w dwóch miejscach, skutki są znaczące, gdyż zamiast
wyrażenia }


\bigskip

$((a-a)+(a\cdot b))+((b+a)\cdot b)\cdot (\frac{a}{b})=\mathit{ab}+a(b+a)$


\bigskip

{\selectlanguage{polish}
otrzymujemy}


\bigskip
$
a+(\sqrt{(a+a)}\cdot (\frac{b}{b}))=a+\sqrt{2a}
$

\bigskip

{\selectlanguage{polish}
Zaznaczyć tu należy, że autorka algorytmu w implementacji stosuje mutację dwupunktową, to znaczy przy
każdorazowej realizacji tego modyfikatora mutowane są dwie pozycje w genie. W aplikacji użytej jako
narzędzie na potrzeby niniejszej pracy użyłem mutacji jednopunktowej m. in celem sprawdzenia różnic w
otrzymanych wynikach. Brak ten jest niejako {\quotedblbase}nadrabiany'' zwiększeniem częstotliwości
występowania tej operacji.}

\subsection[Transpozycja]{\selectlanguage{polish} Transpozycja}
{\selectlanguage{polish}
Transpozonem nazywamy fragment genomu, który ulega transportowi, a dokładniej skopiowaniu i przesunięciu w
obrębie chromosomu. W technice tej rozróżniane są trzy typy transpozycji:}


\begin{itemize}
\item {\selectlanguage{polish}
transpozycja fragmentu zawierającego funkcje i terminale w dowolne miejsce w \textit{głowie}, nie
uwzględniając jednak korzenia poddrzewa, \ ang. \textit{insertion sequence elements }(w odniesieniu do
transpozonu -- dalej jako IS, lub w odniesieniu do transpozycji -- IST),}
\item {\selectlanguage{polish}
transpozycja takiegoż fragmentu, jednak miejscem docelowym staje się korzeń genu, ang. \textit{root insertion
sequence elements} (jak wyżej, odpowiednio RIS i RIST)}
\item {\selectlanguage{polish}
transpozycja całego genu na początek chromosomu.(dalej GT, ang. \textit{gene transposition})}
\end{itemize}

{\selectlanguage{polish}
Rozróżnienie między IS i RIS, wg Autorki, jest pozostałością z okresu rozwoju metody, kiedy to
rozpatrywane były jedynie chromosomy jednogenowe. Mimo to zostały pozostawione w wersji ostatecznej, gdyż w
sposób obrazowy potrafią przedstawić mechanizmy ewolucyjne. Z drugiej zaś strony, po sparametryzowaniu
przebiegu algorytmu, rozróżnienie takie pozwala na lepszą jego kontrolę i {\quotedblbase}dostrojenie''. }

{\selectlanguage{polish}
Podobnie jak w przypadku mutacji, tutaj również występują pewne różnice w wykorzystaniu modyfikacji
między moją aplikacją a propozycją Ferreiry. Mianowicie Autorka stosuje trójstopniową
transpozycję \ IS i RIS, stosując kolejno transpozon jedno-, dwu- i trójelementowy przy każdorazowym
wywołaniu operacji. W swojej implementacji zastosowałem transpozycję pojedynczą z zastosowaniem
tranzpozonu o długości równej 3, zakładając, tak jak przy mutacji, że odpowiedni dobór parametrów
zniweluje tę różnicę.}


\bigskip

\subsubsection[Transpozycja IS]{Transpozycja IS}
{\selectlanguage{polish}
Transpozonem przy IST może być każdy fragment osobnika. Jego początek losowany jest spośród wszystkich pozycji w
obrębie chromosomu. Podobnie losowo wybierana jest jego długość. Destynacja nie może być już w takim
samym stopniu dowolna, więc losowanie ogranicza się do pozycji w \textit{głowach }genów, z wyjątkiem
ich korzeni. Zazwyczaj do IST stosuje się trzy sekwencje IS różnej długości}

{\selectlanguage{polish}
Po dokonaniu losowań, transpozon jest kopiowany i przenoszony w odpowiednie miejsce. Fragment \textit{głowy
}znajdujący się za pozycją docelową zostają przesunięte do tyłu tak daleko, jak pozwala na
to długość \textit{głowy.} Dla przykładu, rozpatrzmy chromosom dwugenowy. Niech \textit{h=8, }do
transpozycji wybrany został element \textit{b+b} na pozycji 7 w genie drugim, zaś docelowym miejscem została
pozycja 4 w genie pierwszym. Otrzymujemy:}

{\selectlanguage{polish}
\ \ \texttt{01234567890123456{\textbar}01234567890123456}}

{\selectlanguage{polish}
\ \ \texttt{-+a-/*+Q\textit{abbabbaaa}{\textbar}*-Qb+*b+\textit{b}\textit{abbaaaab}}

\ \ \ \downarrow

{\selectlanguage{polish}
\ \ \texttt{01234567890123456{\textbar}01234567890123456}}

{\selectlanguage{polish}
\ \ \texttt{-+a-b+b/*\textit{bbabbaaa}{\textbar}*-Qb+*b+\textit{b}\textit{abbaaaab}}

\bigskip

W przełożeniu na drzewa wyrażenia, można pierwszy gen (bowiem tylko on zostaje zmieniony) przedstawić w sposób następujący:
\bigskip

{\selectlanguage{polish}\ttfamily\itshape
$((b^{2}-(a+b))+(\frac{\sqrt{b}}{a}))-a=b^{2}-2a+b+\frac{\sqrt{b}}{a}$\ \ \ \ \ \ \ \ }

\begin{center}
\includegraphics[width=7.594cm,height=3.916cm]{praca-img008.png}
\end{center}

\ \ \ \downarrow

 $((((\frac{b}{b})+(a\cdot b))-b)+b)-a=1+\mathit{ab}-a$

\begin{center}
\includegraphics[width=6.318cm,height=4.392cm]{praca-img009.png}
\end{center}

\bigskip


{\selectlanguage{polish}\ttfamily
\textrm{Jak widać, transpozycja w sposób znaczący wpłynęła na strukturę pierwszego genu,
jednocześnie będącego w dalszym ciągu poprawną syntaktycznie i logicznie konstrukcją. Wynika to z
tego, że -- by zachować rzeczoną spójność i nie dopuścić do rozszerzenia się
}\textrm{\textit{głowy}}\textrm{ -- usunięty został fragment }\textrm{\textit{+Qa. }}\textrm{Część
przed punktem transpozycja, jak i }\textrm{\textit{ogon}}\textrm{ pozostały bez zmian.}}


\bigskip

\subsubsection[Transpozycja z korzeniem.]{Transpozycja z korzeniem}
{\selectlanguage{polish}\ttfamily
\textrm{RIST różni się od poprzedniej operacji tym, że jej celem są zmiany w dolnych częściach
drzewa, od korzenia poczynając. Z racji więc na tę specyfikę, początkiem transposonu musi być
operator funkcyjny}\footnote{Jak zostało wspomniane, rozdzielenie IST i RIST jest reliktem wczesnych wersji
algorytmu i miało charakter raczej praktyczny, niż wynikający z konieczności zachowania prawidłowego jego
działania. Teoretycznie więc niezapewnienie genowi korzenia funkcyjnego nie wpłynęłoby na
poprawność genu. }\textrm{. Przebieg algorytmu podobny jest do transpozycji IS, z dwiema różnicami. Zamiast
losowania destynacji spośród całego chromosomu, wybiera się jedynie gen, na którego początku
podstawiony zostanie transpozon. Po drugie, przy losowaniu początku transpozonu, o ile symbol na wylosowanej
pozycji nie jest operatorem funkcyjnym, wska\'znik przesuwany jest o jedną pozycję w stronę
}\textrm{\textit{ogona}}\textrm{ tak długo, aż na taki operator trafi. Jeśli to nie nastąpi, transpozycja
nie następuje. }}

{\selectlanguage{polish}\ttfamily
\textrm{Przykładowo, niech wybrany do skopiowania będzie fragment }\textrm{\textit{+bQ}}\textrm{, wylosowanym genem
zaś gen drugi, z którego transpozon pochodzi:}}


\bigskip

{\selectlanguage{polish}\ttfamily
\texttt{01234567890123456{\textbar}01234567890123456}}

{\selectlanguage{polish}\ttfamily
\texttt{-+-a/++/\textit{abaaabaaa}{\textbar}*a+\underline{+bQ}-/\textit{babbababb}}}


\ \ \ \downarrow

{\selectlanguage{polish}\ttfamily
\textit{\ \ }01234567890123456{\textbar}01234567890123456}

{\selectlanguage{polish}\ttfamily
\textit{\ \ }-+-a/++/abaaabaaa{\textbar}}\underline{+bQ}*a+\underline{+b}\textit{babbababb}}



\begin{center}
$a + ((b+\sqrt{a})+((a-b)+\frac{b}{a})) = 2a + \sqrt{a} + \frac{b}{a}$
\includegraphics[width=7.634cm,height=4.715cm]{praca-img010.png}
\end{center}

\ \ \ \downarrow

\begin{center}
 $b+\sqrt{a\cdot (b+a+b)}=b+\sqrt{a(a+2b)}$
\includegraphics[width=7.426cm,height=5.56cm]{praca-img011.png}
\end{center}
{\selectlanguage{polish}
Jak widać, zamiana taka drastycznie wpływa na fenotyp. Zachowanie {\quotedblbase}tylnej'' części
\textit{głowy} pozostaje takie samo, jak w przypadku IST. Warto też zauważyć, że w usuwanej część
\textit{głowy} znalazł się też oryginał transpozonu. }


\bigskip

\subsubsection[Transpozycja genu]{\selectlanguage{polish} Transpozycja genu}
{\selectlanguage{polish}
W tym przypadku transpozonem jest cały gen. Zostaje on niejako przesunięty na początek chromosomu,
ponieważ, w przeciwieństwie do poprzednich przypadków, tu oryginał jest usuwany. Jest to dosyć oczywiste
rozwiązanie, biorąc pod uwagę przesunięcie genu uprzednio pierwszego.}

{\selectlanguage{polish}
Na przykład w wariancie trzygenowym:}


\bigskip

{\selectlanguage{polish}
\ \ \texttt{01234567890123456{\textbar}01234567890123456{\textbar}01234567890123456}}

{\selectlanguage{polish}
\ \ \texttt{*+a/+/+Qaabbababb{\textbar}/+b/+Q*/abbabbaab{\textbar}}\texttt{\underline{-Q--Q-Qaaabbababb}}}


\bigskip

{\selectlanguage{polish}
\ \ \texttt{01234567890123456{\textbar}01234567890123456{\textbar}01234567890123456}}

{\selectlanguage{polish}
\ \ \texttt{\underline{-Q--Q-Qaaabbababb{\textbar}}*+a/+/+Qaabbababb{\textbar}/+b/+Q*/abbabbaab}}


\bigskip


\bigskip

{\selectlanguage{polish}
W przypadku problemów arytmetycznych, gdzie funkcją spajającą jest operator dodawania bąd\'z
mnożenia, taka transpozycja może nie dawać wielkich efektów, jednak przy zagadnieniach logicznych bąd\'z
operatory logiczne wykorzystujące, skutki zamiany mogą być co najmniej znaczące. Niech posłuży nam
przykład: niech \textit{F=\{I,N,A,O\},} oznaczające odpowiednio IF ({\quotedblbase}jeśli'', trójargumentowa
\textit{I(X,Y,Z) := jeśli X to Y, w przeciwnym razie Z}), NOT (logiczne zaprzeczenie), AND (koniunkcja), O
(alternatywa). Niech też operatorem łączącym będzie IF. W takim przypadku transpozycja genu
trzeciego, skutkująca postawienia go w roli logicznego poprzednika implikacji, zaś z uprzedniego genu w pozycji
następnika implikacji, kompletnie zmienia efekty działania programu wynikowego.}


\bigskip

\subsection[Krzyżowanie]{\selectlanguage{polish} Krzyżowanie}
{\selectlanguage{polish}
W naturze krzyżowanie, czyli rozmnażanie płciowe, w największym stopniu odpowiada za zwiększanie
różnorodności genetycznej. Stąd też, będący niejako jego odpowiednikiem, modyfikator krzyżowania
(rekombinacji), posiada często wysoki parametr odpowiadający za prawdopodobieństwo jego wystąpienia.
Rekombinacja operuje na dwóch chromosomach. \ Jak wyżej, wyróżnia się trzy typy krzyżowania:}


\begin{itemize}
\item {\selectlanguage{polish}
rekombinacja jednopunktowa (ang. \textit{one-point recombination, }dalej 1PR)}
\item {\selectlanguage{polish}
\ // dwupunktowa (ang. \textit{two-points recombination}, dalej 2PR)}
\item {\selectlanguage{polish}
\ // genu (ang. \textit{gene recombination}, dalej GR)}
\end{itemize}

{\selectlanguage{polish}
Jak we wszystkich modyfikacjach, wszelkie wybory, zarówno chromosomów-rodziców, jak i pozostałych parametrów,
dokonywane są losowo.}


\bigskip

\subsubsection[Krzyżowanie jednopunktowe]{\selectlanguage{polish} Krzyżowanie jednopunktowe}
{\selectlanguage{polish}
Operacja ta polega na zmianie skrzyżowaniu ze sobą dwóch chromosomów. Jest to modyfikacja o tyle ciekawa, że
nie ma tu znaczenia podział chromosomów na geny\footnote{Co prawda, w implementacji ten podział jest
uwzględniony, jednak wynika to z przyjętej przez mnie metody reprezentacji danych i jest kwestią
wtórną.}. Przebieg jest następujący: losowany jest punkt, w którym oba chromosomy zostają
{\quotedblbase}przecięte'', następnie elementy znajdujące się za punktem przecięcia
{\quotedblbase}zamieniają się miejscami''. Najlepiej zaprezentuje to przykład: niech punktem wylosowanym
będzie pozycja 2 w genie drugim (podział między genami zaznaczają jedynie numery pozycji, separatorów
nie użyłem, by nie zaciemniać obrazu):}


\bigskip

{\selectlanguage{polish}\ttfamily
\ \ 012345678012345678012345678}

{\selectlanguage{polish}\ttfamily
\ \ \underline{QQa-aababQ+-aaababaab-bbaaa}}

{\selectlanguage{polish}\ttfamily
\ \ Q-a/baaaaQa-+aaaab/aa-baaaa}


\bigskip


\bigskip

{\selectlanguage{polish}\ttfamily
\ \ 012345678012345678012345678}

{\selectlanguage{polish}\ttfamily
\ \ \underline{QQa-aababQ+}-+aaaab/aa-baaaa}

{\selectlanguage{polish}\ttfamily
\ \ Q-a/baaaaQa\underline{-aaababaab-bbaaa}}


\bigskip


\bigskip

\subsubsection[Krzyżowanie dwupunktowe]{\selectlanguage{polish} Krzyżowanie dwupunktowe}
{\selectlanguage{polish}\ttfamily
\textrm{Ten rodzaj modyfikacji, różni się od poprzedniego faktem, że podział chromosomów macierzystych
następuje w dwóch miejscach, dzieląc je na trzy części. Fragment środkowy służy tu za
materiał genetyczny, który jest wymieniany}\footnote{Faktycznie nie ma znaczenia, czy wymieniany jest fragment
środkowy, czy skrajne, wszak kolejność chromosomów w populacji jest dowolna.}\textrm{. Ponownie,
posłużę się przykładem (niech wybranymi punktami rekombinacji będą pozycje 3. w genie 1. i 5. w
genie 3.):}}


\bigskip


\bigskip

{\selectlanguage{polish}\ttfamily
\ \ 012345678012345678012345678}

{\selectlanguage{polish}\ttfamily
\ \ \underline{-a-*abbbbaa-abbaaa*/a*bbbba}}

{\selectlanguage{polish}\ttfamily
\ \ Q*/aabaaaaQ/Qaabbbbbb-abaab}


\bigskip


\bigskip

{\selectlanguage{polish}\ttfamily
\ \ 012345678012345678012345678}

{\selectlanguage{polish}\ttfamily
\ \ \underline{-a-*}abaaaaQ/Qaabbbbbb-a\underline{bbba}}

{\selectlanguage{polish}\ttfamily
\ \ Q*/a\underline{abbbbaa-abbaaa*/a*b}baab}


\bigskip


\bigskip

{\selectlanguage{polish}\ttfamily
\textrm{Krzyżowanie dwupunktowe daje o wiele większe możliwości uzyskiwania nowych, różnych osobników,
niż wariant jednopunktowy. Co należy zauważyć, w przypadku gdy podział }\textrm{następuje w
częściach }\textrm{\textit{ogonowych}}\textrm{, ingerencja w strukturę poddrzew jest niewielka i podobna
jest do niżej opisanej wymiany genów, z dodatkową (potencjalną) zmianą układu terminali na
liściach poddrzew.}}


\bigskip

\subsubsection[Krzyżowanie genów]{\selectlanguage{polish} Krzyżowanie genów}
{\selectlanguage{polish}
Ostatnim wariantem modyfikatora jest rekombinacja genów. Losowo wybrany gen \ zamieniany jest ze swoim odpowiednikiem
w drugim rodzicu. Przykład (niech genem wylosowanym do krzyżowania będzie gen pierwszy):}


\bigskip

{\selectlanguage{polish}\ttfamily
\textrm{\ \ }012345678{\textbar}012345678{\textbar}012345678}

{\selectlanguage{polish}\ttfamily
\textrm{\ \ }\underline{+Q/Qabbbb{\textbar}QQb*ababa{\textbar}*a**bbaaa}}

{\selectlanguage{polish}\ttfamily
\textrm{\ \ }-*Qaaaabb{\textbar}+b/*ababa{\textbar}-ab/babba}


\bigskip


\bigskip

{\selectlanguage{polish}\ttfamily
\textrm{\ \ }012345678{\textbar}012345678{\textbar}012345678}

{\selectlanguage{polish}\ttfamily
\textrm{\ \ }-*Qaaaabb\underline{{\textbar}QQb*ababa{\textbar}*a**bbaaa}}

{\selectlanguage{polish}\ttfamily
\textrm{\ \ }\underline{+Q/Qabbbb}{\textbar}+b/*ababa{\textbar}-ab/babba}


\bigskip

{\selectlanguage{polish}
GR, choć nie tworzy on nowego materiału genetycznego (żadna ORF nie jest naruszana), jest to istotny modyfikator.
Podobnie jak GT, najciekawsze wyniki wykazuje przy użyciu operatorów logicznych. Mimo to używanie go jako
jedynego (a w każdym razie wiodącego) modyfikatora wymaga znacznej wielkości populacji początkowej, gdyż
w przeciwnym razie ciężko byłoby zagwarantować wystarczającą różnorodności genetyczną.}


\bigskip

\chapter[Rozpatrywane problemy]{\selectlanguage{polish} Rozpatrywane problemy}

\bigskip

{\selectlanguage{polish}
W poniższym rozdziale zaprezentowane zostaną przykłady zastosowań mechanizmu GEP. W żadnej mierze nie
wyczerpują one możliwości tej techniki, pokazują jednak, jak sprawdza się ona w praktyce.
Dokładniejsza analiza wyników uzyskiwanych w zależności od parametryzacji znajduje się w rozdziale 4.}


\bigskip

\section[Odnajdywanie funkcji ]{\selectlanguage{polish} Odnajdywanie funkcji }
{\selectlanguage{polish}
Problem znajdowania funkcji na podstawie podanych jej wartości dla konkretnych argumentów (również z ang.
{\quotedblbase}\textit{symbolic regression}{}'') jest jednym z podstawowych i najprostszych przykładów użycia
algorytmu GEP. W przypadku tym za\textit{ }dane treningowe\textit{ }posłużą pary \textit{a,f(a)}, gdzie
\textit{a} jest losową liczbą rzeczywistą (bąd\'z zespoloną, lecz to implikuje konieczne
modyfikacje struktury chromosomu), \textit{f(a) }zaś wartością szukanej funkcji dla \textit{a. }Aby zapewnić
prawidłowe działanie, używa się także pewnej niewielkiej tolerancji na błąd. \textit{\ }Funkcja
przystosowania przyjęta przez Ferreirę wyraża się wzorem:}

{\selectlanguage{polish}
 $f_{i}=\sum _{j=1}^{C_{t}}(M-|C_{(i,j)}-T_{(j)}|)$\ \ (1)}

{\selectlanguage{polish}
bąd\'z }

{\selectlanguage{polish}
 $f_{i}=\sum _{j=1}^{C_{t}}(M-|\frac{C_{(i,j)}-T_{(j)}}{T_{(j)}}\cdot 100|)$ \ \ (2)}

{\selectlanguage{polish}
dla}

{\selectlanguage{polish}
 $f_{i}$ - wartość funkcji \textit{fitness} dla \textit{i}-tego chromosomu, }

{\selectlanguage{polish}
 $C_{t}$ - liczba danych treningowych,}

{\selectlanguage{polish}
 $C_{(i,j)}$ - wartość wyliczona przez \textit{i}{}-ty chromosom dla \textit{j}-tego \textit{fitness case},}

{\selectlanguage{polish}
 $T_{(j)}$ - faktyczna wartość funkcji szukanej dla \textit{j}-tego \textit{fitness case},}

{\selectlanguage{polish}
 $M$ - zakres selekcji.}

{\selectlanguage{polish}
Wzór zależny jest od tego, czy błąd rozpatrujemy bezwzględnie (1), czy względnie (2). Funkcja taka
prezentuje rozbieżność między wynikiem otrzymanym przez chromosom, a faktycznym wynikom bezwzględnie,
bąd\'z procentowo. }


\bigskip

{\selectlanguage{polish}
Niech za przykład posłuży tu prosta funkcja wielomianowa  $3a^{2}+2a+1$, zaś za dane treningowe
posłużyły pary przedstawione w tabeli 1.}



\begin{center}
\begin{table}
\caption{}
%\tablefirsthead{}
%\tablehead{}
%\tabletail{}
%\tablelasttail{}
\begin{supertabular}{c|c|}
{\selectlanguage{polish}\ttfamily a} &
{\selectlanguage{polish}\ttfamily f(a)}\\\hline
{\selectlanguage{polish}\ttfamily {}-4.2605} &
{\selectlanguage{polish}\ttfamily 46.9346 }\\\hline
{\selectlanguage{polish}\ttfamily {}-2.0437} &
{\selectlanguage{polish}\ttfamily 9.44273 }\\\hline
{\selectlanguage{polish}\ttfamily {}-9.8317} &
{\selectlanguage{polish}\ttfamily 271.324 }\\\hline
{\selectlanguage{polish}\ttfamily 2.7429} &
{\selectlanguage{polish}\ttfamily 29.0563 }\\\hline
{\selectlanguage{polish}\ttfamily 0.7328} &
{\selectlanguage{polish}\ttfamily 4.07659 }\\\hline
{\selectlanguage{polish}\ttfamily {}-8.6491} &
{\selectlanguage{polish}\ttfamily 208.123 }\\\hline
{\selectlanguage{polish}\ttfamily {}-3.6101} &
{\selectlanguage{polish}\ttfamily 32.8783 }\\\hline
{\selectlanguage{polish}\ttfamily {}-1.8999} &
{\selectlanguage{polish}\ttfamily 8.02906 }\\\hline
{\selectlanguage{polish}\ttfamily {}-4.8852} &
{\selectlanguage{polish}\ttfamily 62.8251 }\\\hline
{\selectlanguage{polish}\ttfamily 7.3998} &
{\selectlanguage{polish}\ttfamily 180.071}\\\hline
\end{supertabular}
\end{table}
\end{center}

\bigskip


\bigskip


\bigskip

{\selectlanguage{polish}\ttfamily
 $C_{t}=10,\ \ M=100,\ \ f_{\mathit{max}}=1000$ F=\{-,+,*,/,Q\}, T=\{a\}}

{\selectlanguage{polish}
W tym miejscu należy zaznaczyć, że funkcja pierwiastka kwadratowego stosowana jest z pewnym zabezpieczeniem przed
błędem dziedziny, mianowicie jeśli argument jest mniejszy od zera, funkcja zwraca zero.}

\begin{center}
\begin{table}
\caption{Użyte parametry (\textit{modification rates)}}:
\tablefirsthead{}
\tablehead{}
\tabletail{}
\tablelasttail{}
\begin{supertabular}{|m{4.589cm}|m{4.695cm}|}
\hline
{\selectlanguage{polish} mutacja:} &
{\selectlanguage{polish} 0.5}\\\hline
{\selectlanguage{polish} IST:} &
{\selectlanguage{polish} 0.2}\\\hline
{\selectlanguage{polish} RIST:} &
{\selectlanguage{polish} 0.3}\\\hline
{\selectlanguage{polish} GT:} &
{\selectlanguage{polish} 0.2}\\\hline
{\selectlanguage{polish} 1PR:} &
{\selectlanguage{polish} 0.2}\\\hline
{\selectlanguage{polish} 2PR:} &
{\selectlanguage{polish} 0.2}\\\hline
{\selectlanguage{polish} GR:} &
{\selectlanguage{polish} 0.1}\\\hline
{\selectlanguage{polish} wielkość populacji:} &
{\selectlanguage{polish} 10 os.}\\\hline
{\selectlanguage{polish} liczba genów w chromosomie:} &
{\selectlanguage{polish} 3}\\\hline
{\selectlanguage{polish}\itshape h} &
{\selectlanguage{polish} 4}\\\hline
{\selectlanguage{polish} liczba generacji:} &
{\selectlanguage{polish} 50\footnotemark{}}\\\hline
\end{supertabular}
\end{table}
\end{center}
\footnotetext{Faktycznie liczba populacji wynosiła 51, gdyż początkowa generacja została liczona jako
zerowa.}

\bigskip

{\selectlanguage{polish}
Do wyliczenia \textit{fitness} użyty został wzór (.1), zaś margines błędu ustalony został na 0.01 w
skali chromosomu dla każdego \textit{fitness case}. W jednym z udanych\footnote{Za udany uznaję tu przebieg, w
którym odnaleziona została prawidłowa funkcja, tzn chromosom z \textit{fitness} = 1000} przebiegów algorytmu,
rozwiązanie zostało odnalezione w generacji dziesiątej. }


\bigskip

{\selectlanguage{polish}
Początkowa losowa populacja:}


\bigskip

{\selectlanguage{polish}\ttfamily
gen 1. \ \ {\textbar} gen 2. \ {\textbar} gen 3. \ {\textbar} \ \ fitness\ \ }

{\selectlanguage{polish}\ttfamily
aaaaaaaaa{\textbar}/a+/aaaaa{\textbar}QQa/aaaaa{\textbar} : 139.093}

{\selectlanguage{polish}\ttfamily
/aa+aaaaa{\textbar}+a**aaaaa{\textbar}*/a*aaaaa{\textbar} : -1579.7}

{\selectlanguage{polish}\ttfamily
aa+aaaaaa{\textbar}aaQaaaaaa{\textbar}*aaaaaaaa{\textbar} : 395.753}

{\selectlanguage{polish}\ttfamily
aa/*aaaaa{\textbar}+aa*aaaaa{\textbar}a+a/aaaaa{\textbar} : 50.0205}

{\selectlanguage{polish}\ttfamily
{}-aQaaaaaa{\textbar}*/*+aaaaa{\textbar}/a/+aaaaa{\textbar} : 699.796}

{\selectlanguage{polish}\ttfamily
a+aaaaaaa{\textbar}aaaQaaaaa{\textbar}+Q*+aaaaa{\textbar} : 403.153}

{\selectlanguage{polish}\ttfamily
a-Qaaaaaa{\textbar}QQaaaaaaa{\textbar}Q-aaaaaaa{\textbar} : 126.796}

{\selectlanguage{polish}\ttfamily
Qaa*aaaaa{\textbar}aaa/aaaaa{\textbar}a*aaaaaaa{\textbar} : 103.862}

{\selectlanguage{polish}\ttfamily
aaa-aaaaa{\textbar}Qaaaaaaaa{\textbar}Qa+*aaaaa{\textbar} : 133.4}

{\selectlanguage{polish}\ttfamily
a/aaaaaaa{\textbar}//+aaaaaa{\textbar}++**aaaaa{\textbar} : 692.833}


\bigskip

{\selectlanguage{polish}
Jak widać, początkowe wartości dalekie są od zadowalających. Jednak, co zobaczyć można na
wykresie\footnote{Dane do wykresu oraz szczegółowy zapis przebiegu algorytmu w załączniku nr}, już w
drugiej generacji znaleziony został fenotyp bliski ideałowi (\textit{fitness }\ = 955,945), przy czym średnia
wartość przez cały czas nie odbiega znacząco od średniej początkowej.}



\begin{center}
\begin{minipage}{15.423cm}

\bigskip

{\itshape
Wykres \stepcounter{Wykres}{\theWykres}: Zachowanie funkcji fitness dla problemu szukania funkcji}

\includegraphics[width=16.925cm,height=6.249cm]{"wykres1.jpg"}
\end{minipage}
\end{center}

\bigskip

{\selectlanguage{polish}
Generacja finalna, zawierająca poprawne rozwiązanie:}


\bigskip

{\selectlanguage{polish}\ttfamily
gen 1. \ \ {\textbar} gen 2. \ {\textbar} gen 3. \ {\textbar} \ \ fitness\ \ }

{\selectlanguage{polish}\ttfamily
*/a*aaaaa{\textbar}/a+aaaaaa{\textbar}++**aaaaa{\textbar} : 955.945}

{\selectlanguage{polish}\ttfamily
/aaaaaaaa{\textbar}Qaaaaaaaa{\textbar}/aaQaaaaa{\textbar} : 172.472}

{\selectlanguage{polish}\ttfamily
//+*aaaaa{\textbar}+aaaaaaaa{\textbar}a*+aaaaaa{\textbar} : 79.3252}

{\selectlanguage{polish}\ttfamily
//+*aaaaa{\textbar}+aaaaaaaa{\textbar}a*+aaaaaa{\textbar} : 79.3252}

{\selectlanguage{polish}\ttfamily
//+*aaaaa{\textbar}+aaaaaaaa{\textbar}a*+aaaaaa{\textbar} : 79.3252}

{\selectlanguage{polish}\ttfamily
+aaaaaaaa{\textbar}+aaaaaaaa{\textbar}+aaaaaaaa{\textbar} : 0.7707}

{\selectlanguage{polish}\ttfamily
//+*aaaaa{\textbar}+aaaaaaaa{\textbar}a//+aaaaa{\textbar} : 79.3252}

{\selectlanguage{polish}\ttfamily
//+*aaaaa{\textbar}+aaaaaaaa{\textbar}a-+aaaaaa{\textbar} : 79.3252}

{\selectlanguage{polish}\ttfamily
//+*aaaaa{\textbar}//aaaaaaa{\textbar}*+aaaaaaa{\textbar} : 746.4}

{\selectlanguage{polish}\ttfamily
//a*aaaaa{\textbar}*+a+aaaaa{\textbar}+aaaaaaaa{\textbar} : 1000}

\bigskip

{\selectlanguage{polish}
Mimo iż przedstawiony problem nie był skomplikowany, nie w każdym z eksperymentów (przy podanych parametrach)
rozwiązanie jest odnajdywane, choć w większości przypadków wyniki bardzo bliskie są szukanej
funkcji. Niech za przykład posłuży przebiega algorytmu, w którym sukces nie został osiągnięty.
Przy identycznych parametrach, już w drugiej populacji wyewoluował osobnik o dostosowaniu niezmiernie
zbliżonym do maksimum. Po kolejnych \ dziewięciu iteracjach powstał chromosom, który pierwszeństwo
zachował do końca działania algorytmu. Rzeczony chromosom oraz jego fenotyp:}

\bigskip

{\selectlanguage{polish}\ttfamily
\ \ \ \ +**+aaaaa\ \ {\textbar}\ \ aaa*aaaaa\ \ {\textbar}\ \ \ \ aaaaaaaaa}


 $((a+a)\cdot a)+(a\cdot a)\ \ +\ \ a\ \ +\ \ a\ \ =\ \ 3a^{2}+2a$

\begin{center}
\includegraphics[width=14.566cm,height=4.763cm]{"praca-img013.png"}
\end{center}
{\selectlanguage{polish}
Wykres 2. przedstawia przebieg funkcji dostosowania w przebiegu, w którym rozwiązanie takie zostało
odnalezione, wykres obu funkcji (odnalezionej, oznaczonej kolorem czerwonym, oraz docelowej, oznaczonej kolorem
niebieskim) ilustruje na wykres 3.}

{\centering \par}
\begin{center}
\begin{minipage}{16cm}
{\itshape
Wykres \stepcounter{Wykres}{\theWykres}: Przebieg funkcji dostosowania}
\includegraphics{"wykres2.jpg"}
\end{minipage}
\end{center}


{\centering \par}
\begin{center}
\begin{minipage}{13.229cm}
{\itshape
Wykres \stepcounter{Wykres}{\theWykres}: Kolorem niebiskim oznaczona została funkcjia szukana, czerwonym zaś
funkcja odnaleziona}
\includegraphics[width=13.229cm,height=13.229cm]{"praca-img015.png"}
\end{minipage}
\end{center}

{\selectlanguage{polish}
Dokładniejsza analiza wyników uzyskiwanych przez GEP dla problemu znajdowania funkcji znajduje się w
poniżej.}


\bigskip

\section[Problemy klasyfikacyjne]{\selectlanguage{polish} Problemy klasyfikacyjne}
{\selectlanguage{polish}
Mechanizm GEP można także z powodzeniem wykorzystywać w problemach związanych ze zgłębianiem danych, w
szczególności w zagadnieniach klasyfikacyjnych. Klasyfikacja polega (w pewnym uproszczeniu) na odgadnięciu
parametru docelowego na podstawie parametrów znanych (przesłanek). Zazwyczaj stosuje się implikację
JEśLI {\textless}przesłanki{\textgreater} TO {\textless}wniosek{\textgreater}, gdzie wniosek to klasa, do jakiej
zaliczamy rozpatrywaną jednostkę (\textit{entity}). W tym przypadku również stosuje się tzw. dane
uczące. Jako funkcję przystosowania przyjmuje się zazwyczaj stosunek przypadków zaklasyfikowanych
prawidłowo do przypadków zaklasyfikowanych błędnie. W implementacji użyłem metody zaproponowanej przez
Lopesa ([6]). Funkcja jest iloczynem dwóch wartości: czułości (ang. \textit{Sensitivity}) \textit{Se }i
swoistości (bąd\'z specyficzność, ang. \textit{specificity}) \textit{Sp} określających skuteczność
prawidłowego rozpoznania \ odpowiednio przypadków poprawnie uznanych jako należące do swojej klasy
(\textit{true positive, {\quotedblbase}faktycznie dodatnich''}) i poprawnie z odpowiedniej klasy wykluczonych
(\textit{true negative, {\quotedblbase}faktycznie ujemnych''}). Niech za ilustrację tych pojęć posłuży
przykład diagnozy medyczne, gdzie przyjmujemy dwie klasy: wykrycie choroby (diagnoza pozytywna) bąd\'z uznanie
pacjenta za zdrowego (diagnoza negatywna). Za wynik faktycznie dodatni uznamy prawidłowe wykrycie u pacjenta
choroby, zaś fałszywie dodatni -- orzeczenie u zdrowego pacjenta choroby. Analogicznie, wynikiem prawdziwie
ujemnym będzie uznanie zdrowym pacjenta zdrowego, z kolei fałszywie ujemnym -- nie wykrycie choroby u pacjenta
na nią cierpiącego. Parametry te określa się wzorami:}

{\selectlanguage{polish}
 $\mathit{Se}=\frac{\mathit{tp}}{\mathit{tp}+\mathit{fn}}$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)}

{\selectlanguage{polish}
 $\mathit{Sp}=\frac{\mathit{tn}}{\mathit{tn}+\mathit{fp}}$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)}


\bigskip

{\selectlanguage{polish}
gdzie \textit{tp} oznacza liczbę przypadków faktycznie dodatnich, \textit{tn} -- faktycznie ujemnych, \textit{fp}
-- błędnie dodatnich, \textit{fn} -- błędnie ujemnych. W analogii do szpitala, czułość równa 1
oznacza, że wszyscy pacjenci chorzy zostaną jako tacy oznaczeni, zaś specyficzność o tej wartości
oznacza, że wszyscy zdrowi pacjenci zostaną {\quotedblbase}zwolnieni do domu''.}


\bigskip

{\selectlanguage{polish}
Ze względu na typ wartości parametrów, problemy klasyfikacyjne można podzielić na problemy z parametrami
logicznymi i rzeczywistymi. Drugim rozróżnieniem może być liczba klas. }

{\selectlanguage{polish}
Jeśli wartościami terminalnymi mogą zostać jedynie logiczne \textit{prawda }i \textit{fałsz, }problem zdaje
się być trywialny, wystarczy wykorzystać operatory logiczne bezpośrednio na terminalach z tego zbioru .
Inaczej wygląda to, jeśli algorytm działać ma na wartościach rzeczywistych. Ferreira w \cide{Ferreira.mmbaa} proponuje
niezmodyfikowaną wersję algorytmu. Za przykład podając test diagnostyczny na typ raka piersi (opisane
szerzej w rozdziale 5.3), wykorzystuje zbiór operatorów funkcyjnych\textit{ F=\{+, -, *, /, {\textless},
{\textgreater}, :, \$, =, !\}} , gdzie ostatnie sześć symboli oznacza odpowiednio \textit{mniejszy od, większy
od, mniejszy lub równy, większy lub równy, równy, różny. }Po wykonaniu porównania, jeśli wynikiem jest prawda,
zwracana jest pierwsza wartość, jeśli fałsz -- druga. Za funkcję przystosowania Autorka przyjęła
implikację:}
\bigskip
jeśli $n>C_{p}$,\ to\ $f_{i}=n$,\ w przeciwnym wypadku\ $f_{i}=0$
\bigskip

W eksperymencie przez nią opisywanym wykorzystano zestaw 350-ciu danych treningowych, oraz 174 danych testowych.
Wynikiem diagnostyki może być jedna z dwóch klas: B -- nowotwór łagodny (ang. {\quotedblbase}\textit{benign
tumor}'') oraz M -- nowotwór złośliwy (ang. {\quotedblbase}\textit{malignant}''). Osobniki mają tu
postać chromosomów trójgenowych, przy czym każdy z genów odpowiada za osobną regułę. 
Z racji tego, że liczba klas równa jest 2, interpretacja wyniku zwracanego przez regułę (będącego
liczbą rzeczywistą) nie stanowi wielkiego problemu. Zastosowany został próg zaokrąglenia
zero-jedynkowego (ang. \textit{0/1 rounding threshold}) \textit{Rt}, powyżej którego za wynik przyjmuje się
wartość 1, poniżej zaś -- 0. W tym przypadku, \textit{Rt}=0.
Algorytm został uruchomiony dla populacji składającej się z 50 osobników o długości
\textit{glowy h=}8. Rozwiązanie oraz jego fenotyp przedstawione zostało na rysunku 4. 



\begin{center}
\begin{minipage}{10.478cm}
{\itshape
Rysunek \stepcounter{Drawing}{\theDrawing}: a) chromosom będący wynikiem testu diagnostycznego, oraz b) jego
fenotyp w formie drzew (\'zródło: \cite{Ferreira.anaafsp})}

\includegraphics[width=10.478cm,height=12.912cm]{"praca-img016.jpg"}
\end{minipage}
\end{center}
\bigskip
{\selectlanguage{polish}
Rozwiązanie to spośród 350 danych treningowych poprawnie oznaczyło 340 z nich, zaś spośród 174 danych
testowych osiągnęło 173 poprawnych wyników, co daje błąd klasyfikacyjny równy 0,575\%,
skuteczność zaś równą 97,143\%. }


\bigskip

{\selectlanguage{polish}
\ Innym z możliwych rozwiązań jest to zaproponowane przez autorów systemu GEPCLASS (\cite{gepclass}). W tym przypadku użyty został zbiór symboli funkcyjnych
\textit{F=\{I,O,A,N\}} złożony z odpowiednio implikacji, alternatywie, koniunkcji i zaprzeczeniu. Ponadto, jak
wyżej, znak {\quotedblbase}\texttt{!}{}'' używany będzie jako relacja różności. }

{\selectlanguage{polish}
Autorzy założyli, że liść stanowić będzie strukturę dwuelementową, złożoną z
parametru oraz numeru atrybutu. Takie podejście pociąga jednak za sobą daleko idące zmiany zarówno w
strukturze osobników i w mechanizmach modyfikacji, jak i w implementacji, wprowadza bowiem dodatkowy zbiór
operatorów relacyjnych. Stanowią one niejako trzeci człon genu (po \textit{głowie }i \textit{ogonie}). }

{\selectlanguage{polish}
Przykładowa ORF oraz drzewo parsowania prezentujące takie podejście przedstawione zostały na rysunku 5.}


\bigskip

{\selectlanguage{polish}\ttfamily
pozycja: \ \  \ 0 1 2 3 \ 4 \ \ 5}

{\selectlanguage{polish}\ttfamily
wartość:\ \  \ \  O N = {\textless} b{\textbar}2 a{\textbar}3}

{\selectlanguage{polish}\ttfamily
fenotyp:\ \ \ \ (\~{}b{\textless}2 OR a=3)}



\begin{center}
\begin{minipage}{11.511cm}
{\itshape
Rysunek \stepcounter{Drawing}{\theDrawing}: Otwarta ramka odczytu, fenotyp oraz jego reprezentacja na drzewie}
\includegraphics{"praca-img017.png"}
\end{minipage}
\end{center}

{\selectlanguage{polish}
Bazując na tej metodzie użyłem podobnego rozwiązania. Z jednej strony pokazuje ono elastyczność
modelu GEP, z drugiej zaś może okazać się skuteczniejsze niż propozycja Ferreiry w przypadkach, o
parametrach parami różnych o rzędy wielkości.}

{\selectlanguage{polish}
Nadal konieczne są tu modyfikacje działania, ale nie są tak daleko idące. Przede wszystkim zmieniona
zostaje struktura genu oraz jego translacji. Tutaj operatory relacyjne umieszczane są w terminalach, jednak
nałożone zostają pewne restrykcje. Niech więc gen zapisany zostanie w postaci:}


\bigskip

{\selectlanguage{polish}\ttfamily
pozycja\ \ :\ \ 0 1 \ 2 \ \ 3 \ \ 4 \ \ 5 \ \ 6}

{\selectlanguage{polish}\ttfamily
wartość \ : \ I I a=1 b=2 c=3 d=3 e=4}


\bigskip

{\selectlanguage{polish}
Przy takim podejściu, liście stają się trójką \{\textit{a,r,n}\} gdzie \textit{a} jest termem, \textit{r
}należy do zbioru operatorów relacyjnych, \textit{n} zaś oznacza identyfikator z tablicy wartości danego
parametru spośród wszystkich danych uczących. Oznacza to, że w implementacji konieczne jest uprzednie
zczytanie i przechowywanie owych wartości (przechowywane są jedynie wartości unikalne, tzn. żadna wartość
nie powtarza się w tablicy, dane nie są również poddane sortowaniu, które znacznie zwiększałoby
złożoność obliczeniową algorytmu). }

{\selectlanguage{polish}
Powyższy gen jest więc tłumaczony na poniższe drzewo:}


\bigskip



\begin{center}
\includegraphics[width=8.149cm,height=3.863cm]{"praca-img018.png"}
\end{center}
{\selectlanguage{polish}
Zakładając taką strukturę genów, zmiany w operacjach modyfikacji mają charakter jedynie
implementacyjny.}


\bigskip

{\selectlanguage{polish}
Sam fenotyp nie zawsze daje jednak odpowiedzi, do której klasy zaklasyfikować rozpatrywany. przypadek. W sytuacji,
gdy rezultatem może być jedynie wartość \textit{prawda }bąd\'z \textit{fałsz}, problem nie zachodzi,
ponieważ poddrzewa takież wartości zwracają (można by wręcz potraktować to jako szczególny
przypadek szukania funkcji, przy czym parametry mają wartości zero-jedynkowe). Inaczej jest jednak, gdy klas jest
więcej, żadne poddrzewo nie może jednoznacznie wskazać numeru klasy. Jednym z możliwych rozwiązań
jest założenie, że każdy gen w chromosomie odpowiada konkretnej klasie. Liczba genów jest więc równa
liczbie klas. Przykładowo, niech dany będzie zbiór klas \textit{\{C1, C2, C3\}} oraz chromosom:}


\bigskip

{\selectlanguage{polish}
gen\ \ 
\ \texttt{Ia!8a{\textless}10a=5d{\textgreater}1d{\textless}4a{\textless}3{\textbar}OIc=3a=7c{\textless}2b{\textgreater}0b!3{\textbar}d!2Oa{\textgreater}1b{\textless}7c{\textgreater}2a!7c{\textgreater}3}}

{\selectlanguage{polish}
wartość \ \  \texttt{\ \ \ \ T\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\ \ \ \ \ \ \ \ \ \ \ \ \ \ F}}


\bigskip

{\selectlanguage{polish}
gdzie \texttt{T }oznacza logiczną \textit{prawdę}\texttt{, F }zaś \textit{fałsz}. Rozpatrywany przypadek z
danych uczących należy do klasy \textit{C2, }co zostało prawidłowo rozpoznane przez gen drugi
(\textit{tp}). Gen trzeci również dał prawidłową odpowied\'z, zwracając wartość \textit{fałsz
}(\textit{tn}), {\quotedblbase}pomylił'' się jednak gen pierwszy, zwracając \textit{prawdę}
(\textit{fp}) (mimo iż każdy \textit{fitness case} jest liczony niejako trzy razy, proporcje \textit{Se }i
\textit{Sp }pozostają bez zmian).}

\bigskip

{\selectlanguage{polish}
Przykładowy rezultat uzyskany dla problemu klasyfikacji odmiany irysów\footnote{Frank, A. \& Asuncion, A. (2010).
UCI Machine Learning Repository. Irvine, CA: University of California, School of Information and Computer Science}.
Jako danych treningowych użyto zestawu stu pięćdziesięciu przypadków składających się z
czterech parametrów oraz klasy. Parametry liczbowe opisują tu cechy kielicha kwiatu, odpowiednio długość
(\textit{a}) i szerokość (\textit{b}) działki kielicha oraz długość (\textit{c}) i szerokość
(\textit{d}) płatka, wyrażane w centymetrach. Wynikiem wnioskowania może być jedna z trzech klas: \textit{Iris
setosa}, \textit{Iris versicolor} oraz \textit{Iris virginica}. Na każdą odmianę przypadało 50 zestawów
danych. Algorytm został uruchomiony z następującymi parametrami zawartymi w tabeli 3.}

{\selectlanguage{polish}\itshape
Tabela 3\textup{.}}

\begin{center}
\begin{table}
\caption{}
\tablefirsthead{}
\tablehead{}
\tabletail{}
\tablelasttail{}
\begin{supertabular}{|m{4.4040003cm}|m{4.642cm}|}
\hline
{\selectlanguage{polish} terminale: } &
{\selectlanguage{polish} \{\textit{a,b,c,d}\}}\\\hline
{\selectlanguage{polish} funkcje:} &
{\selectlanguage{polish} \{\textit{I,N,A,O}\}}\\\hline
{\selectlanguage{polish} genów na chromosom:} &
{\selectlanguage{polish} 3}\\\hline
{\selectlanguage{polish} \textit{h}:} &
{\selectlanguage{polish} 4}\\\hline
{\selectlanguage{polish} generacji:} &
{\selectlanguage{polish} 10}\\\hline
{\selectlanguage{polish} populacja:} &
{\selectlanguage{polish} 30os}\\\hline
{\selectlanguage{polish} mutacja:} &
{\selectlanguage{polish} 0.1}\\\hline
{\selectlanguage{polish} IST:} &
{\selectlanguage{polish} 0.1}\\\hline
{\selectlanguage{polish} RIST:} &
{\selectlanguage{polish} 0.1}\\\hline
{\selectlanguage{polish} GT:} &
{\selectlanguage{polish} 0.1}\\\hline
{\selectlanguage{polish} 1PR:} &
{\selectlanguage{polish} 0.2}\\\hline
{\selectlanguage{polish} 2PR:} &
{\selectlanguage{polish} 0.5}\\\hline
{\selectlanguage{polish} GR:} &
{\selectlanguage{polish} 0.1}\\\hline
\end{supertabular}
\end{table}
\end{center}



{\selectlanguage{polish}
Osobnik o najwyższej mierze dostosowania został odnaleziony w siódmej populacji, i choć wartość
\textit{fitness} była względnie wysoka (równa 0.633733), nadal daleka od maksimum. Rozwiązanie zakodowane
zostało w chromosomie :}



{\selectlanguage{polish}\ttfamily
gen 1.:
\ \ d{\textless}5a!4Id!15c=40b{\textless}3d{\textless}6c{\textless}19b{\textless}0c{\textgreater}23a=26a{\textgreater}25b!10}

{\selectlanguage{polish}\ttfamily
gen
2.:\ \ c=31b{\textgreater}16Ob=18a=29d{\textgreater}3b!17b{\textgreater}17b{\textgreater}11c!40d{\textgreater}9d=3a=5}

{\selectlanguage{polish}\ttfamily
gen 3.:\ \ Ac{\textgreater}9OAa!24b!13b{\textless}2c!24c{\textless}17b=0a!13d{\textgreater}18b!21}



{\selectlanguage{polish}
Otwarte ramki odczytu zostały oznaczone podkreśleniem. Jak zostało wspomniane, wartości liczbowe zawarte w
chromosomie odpowiadają identyfikatorowi w tablicy możliwych (tzn. występujących w danych treningowych)
wartości parametru, do którego są przyrównywane. W tym przypadku rozpatrywane były wszystkie cztery
sparametryzowane cechy badanych kwiatów. Niech \ tablica przedstawiona będzie w postaci \ \texttt{c[i]=d}, gdzie
\texttt{c} należy do zbioru termów, \texttt{i} jest kluczem tablicy, \texttt{d} stanowi wartość parametru z
danych uczących. Przy tym zestawie treningowym i tym konkretnym chromosomie, wykorzystujemy:}

{\selectlanguage{polish}\ttfamily
a[24]=5,6}

{\selectlanguage{polish}\ttfamily
b[2]=3,2}

{\selectlanguage{polish}\ttfamily
b[13]=4,1}

{\selectlanguage{polish}\ttfamily
c[9]=4,7}

{\selectlanguage{polish}\ttfamily
c[31]=5,8}

{\selectlanguage{polish}\ttfamily
d[5]=0,6}


\bigskip

{\selectlanguage{polish}
Fenotypem osobnika jest więc zestaw trzech reguł:}


\bigskip

{\selectlanguage{polish}\ttfamily
Jeśli (\textit{d} {\textgreater} 0,6cm), to \textit{Iris setosa}}

{\selectlanguage{polish}\ttfamily
Jeśli\textit{ }(\textit{c} ${\neq}$ 4,1cm\textit{)}, to \textit{Iris versicolor} }

{\selectlanguage{polish}\ttfamily
Jeśli (\textit{c }{\textgreater} 4,7cm) i ((\textit{b} ${\neq}$ 4,1cm i \textit{b} {\textless} 3,2cm) lub (\textit{a
}${\neq}$ 5,6cm)), to \textit{Iris virginica}.}


\bigskip

{\selectlanguage{polish}
Co ciekawe, mimo iż długość \textit{głowy} została ustawiona na 4, co daje całkowitą
długość genu równą 13, dwie z trzech reguł składowych zawierały się w jednym terminalu. Mimo
to reguły te prawidłowo oznaczyły niemal wszystkie przypadki należące do klas pierwszej i trzeciej jako
należące właśnie do nich i tylko do nich. Zdecydowanie gorzej poradziły sobie z gatunkiem \textit{Iris
versicolor, }gdzie żaden zestaw treningowy nie został prawidłowo oznaczony. Wska\'zniki czułości oraz
swoistości wyniosły odpowiednio: 0,97 (klasyfikacja negatywna niemal stuprocentowo skuteczna) i 0.653333 (niewiele
ponad dwie trzecie zostało poprawnie oznaczone jako należące do danej klasy).}


\bigskip

{\selectlanguage{polish}
Zachowanie funkcji fitness w tym eksperymencie prezentuje wykres 4.}



\begin{center}
\begin{minipage}{14.811cm}

\bigskip

{\centering\itshape
Wykres \stepcounter{Wykres}{\theWykres}: Zmiany wartości najlepszej oraz średniej wartości fitness dla
przykładu klasyfikacji irysów.
\par}

\includegraphics[width=13.778cm,height=6.802cm]{"wykres4.jpg"}
\end{minipage}
\end{center}

\bigskip


\bigskip


\bigskip

\chapter[Implementacja]{\selectlanguage{polish} Implementacja}

\bigskip

{\selectlanguage{polish}
\ Program stworzony na potrzeby tej pracy, napisany został w języku C++ z wykorzystaniem pewnych idei
konstrukcyjnych wzorców projektowych (\cite{wzorce}). Wszelkie dane wejściowe przekazywane są w pliku, zawierającym
informacje, jakiego typu jest rozpatrywany problem, jakie symbole funkcyjne i terminalne mają zostać użyte,
parametry oraz dane uczące. Dane te przekazywane są do obiektu klasy \texttt{Box}, który następnie
przekazywany jest do pozostałych klas. Aby program miał charakter bardziej uniwersalny, metody oraz inne elementy
charakterystyczne dla rozpatrywanego problemu realizowane są w klasach dziedziczących. Aby to
osiągnąć, klasy \texttt{Box}, \texttt{Chromosome} oraz \texttt{Gene} posiadają pewne cechy podobne do
{\quotedblbase}budowniczego'' czy {\quotedblbase}fabryki abstrakcyjnej'' (por. \cite{wzorce}) {\quotedblbase}produkujące''
właściwy egzemplarz odpowiednio populacji, genu i drzewa wyrażenia. Przedstawione to zostało na diagramie
klas na Rysunku 6\footnote{Na diagramie strzałki z prostym grotem oznaczają składnik klasy o nazwie
widniejącej przy strzałce, grot pusty w środku oznacza dziedziczenie. Oznaczenia łączą się, tzn
grot biały z kreską w środku oznacza składnik klasy \ dziedziczący po niej.}. }

\begin{center}
\begin{minipage}{17cm}
{\itshape
Rysunek \stepcounter{Drawing}{\theDrawing}: Diagram klas}
\includegraphics[width=17cm,height=14.307cm]{"praca-img020.png"}\end{minipage}
\end{center}

{\selectlanguage{polish}
Jak widać, \foreignlanguage{english}{klasy }odzwierciedlające elementy występujące w opisie teoretycznym i
niejako w przyrodzie,\foreignlanguage{english}{ }są klasami abstrakcyjnymi, po których dziedziczą klasy
specyficzne dla problemu. Wszelkie operacje {\quotedblbase}kanoniczne'' realizowane są w ich obrębie, jednak,
jeśli zajdzie taka potrzeba, mogą zostać nadpisane w klasach dziedziczących. Przykładem może
służyć tu operacja zwracająca losowy terminal w przypadku klasyfikacji opisanej powyżej. Metoda
\texttt{Chromosome::getRandTerm()}\footnote{Zapis należy odczytywać jako [klasa]::[metoda], czyli [metoda] klasy
[klasa]} domyślnie zwraca pojedynczy symbol, tak jak przewiduje to klasyczna wersja implementacji. Przy klasyfikacji
zachodzi jednak konieczność otrzymania napisu co najmniej trzyznakowego, co znajduje wyraz w metodzie
\texttt{CLChromosome::getRandTerm().}}

{\selectlanguage{polish}
Podejście takie rozwiązuje również problem implementacji funkcji przystosowania - \ racji tego, że
\textit{fitness} obliczana jest dla każdego chromosomu, a różnorodność rozwiązywanych problemów jest
trudna do ograniczenia, w klasie nadrzędnej \texttt{Chromosome} metoda \texttt{fitness}() jest jedynie funkcją
wirtualną, a faktyczna realizacja ma miejsce w klasach dziedziczących.}

{\selectlanguage{polish}
Dodatkowo, oprócz obiektów pojawiający się w opisie teoretycznym algorytmu, pojawiają się klasy
odpowiadające za konstrukcję drzewa oraz wykonywanie programów-fenotypów: klasa \ wirtualna
\texttt{ExpressionNode} oraz dziedziczące po niej klasy zależne od rozpatrywanego zadania. Te z kolei
stanowią klasy nadrzędne dla reprezentantów wierzchołków drzewa -- \texttt{XXOperNode} (operatory) oraz
\texttt{XXVarNode} (terminale, liście), gdzie \texttt{XX} są przedrostkiem właściwym dla problemu. }

{\selectlanguage{polish}
W przypadku rozbudowy programu pod kątem obsługi innych problemów, oprócz zaimplementowania klas
dziedziczących, pamiętać należy o zdefiniowaniu symbolu zagadnienia w pliku \textit{Box.h} (
\texttt{\#define {\textless}PROBLEM{\textgreater} {\textless}int{\textgreater}}) oraz o modyfikacji w obrębie
metod:}



\begin{itemize}
\item {\selectlanguage{polish}
\texttt{Box::loadData()}: w tym miejscu zczytywane zostają dane wejściowe, wśród których znajduje się
oznaczenie problemu, tu również należy zadbać, by został odpowiednio rozpoznany i przekazany do publicznej
zmiennej \texttt{\textit{problem}}\textit{ }klasy \texttt{Box};}
\item {\selectlanguage{polish}
\texttt{Box::Init()}: w związku z przyjętym przeze mnie podejściem, inicjowanie iteracji oraz warunków jej
zakończenia pozostaje w gestii użytkownika/developera platformy i realizowane są w podprogramie głównym
(funkcji main()). Oznacza to, że warunek zakończenia, tj. wartość maksymalna funkcji przystosowania, znajdować
musi się poza klasą Population (tworzona jest ona zawsze wewnątrz pętli iteracyjnej, którą ten
warunek zamyka). Stąd {\quotedblbase}sztywne'' ustawienie go w rzeczonej metodzie.}

{\selectlanguage{polish}
Podobnie rzecz ma się z wartością \textit{n }maksymalnej arności, wykorzystywaną do wyznaczania
długości \textit{ogona}. Jest to konsekwencja przyjętej koncepcji klasy Box jako {\quotedblbase}pudełka z
parametrami''. }
\item {\selectlanguage{polish}
\texttt{Box::createPopulation(): }ostatnia w przebiegu programu metoda, w której sprawdzana jest zmienna problemu.,
jest to także niejako metoda wytwórcza odpowiedniej populacji, o której wspomniałem wyżej.}
\end{itemize}

\bigskip



{\selectlanguage{polish}
Jako że spektrum problemów, w których mechanika GEP mogłaby znale\'zć zastosowanie jest szerokie, w
implementacji skupiłem się na dwóch opisanych powyżej. Jak pokazuje przykład problemu klasyfikacji, w
niektórych zastosowaniach konieczne stają się pewne modyfikacje modelu teoretycznego, w tym przypadku
reprezentacja liści drzewa parsowania. Z tego też powodu, mimo że chromosomy nadal przechowywane są w postaci
tekstowej, wszelkie modyfikacje wykonywane są na wektorach znaków. Nie należy jednak sądzić, że przeczy
to poprzedniemu stwierdzeniu, jakoby GEP nie wymagał kontroli spójności. {\quotedblbase}Oryginalny'' GEP nie
jest bowiem przystosowany do porównywania wartości liczbowych i zwracaniu wartości logicznych. Zmianę tę
można więc raczej uznać za rozszerzenie abstrakcji terminali, niż zubożenie algorytmu przez dodanie
warunków modyfikacji.}

{\selectlanguage{polish}
{\quotedblbase}Zmiany pokoleniowe'' inicjalizowane są klasie \texttt{Population}. Zgodnie z opisem przedstawionym w
rozdziale 2., pierwsza populacja wygenerowana zostaje zupełnie losowo (co sygnalizowane jest przekazaniem do
konstruktora klasy flagi równej 1). Obliczanie wartości \textit{fitness} (w tym przeliczanie jej na wartości
procentowe) realizuje metoda \texttt{Population::getFitness()}, wyniki której przechowywane są w tablicach jako
prywatne składniki. }

{\selectlanguage{polish}
Za tworzenie nowej populacji odpowiada metoda \texttt{Population::makeNew()}, zwracająca wska\'znik do kolejnej
generacji. Przebieg działania tej funkcji nie odbiega od modelu teoretycznego -- na początku kopiowany jest
osobnik o najlepszym dostosowaniu, następnie następuje selekcja ruletkowa. Następnym etapami są kolejne
modyfikacje genetyczne, których liczba zależna jest od podanych w danych wejściowych parametrów. Wszystkie one
stanowią osobne metody, które losują chromosom do modyfikacji, a następnie wywołują
właściwą metodę już w klasie \texttt{Chromosome}. Wyjątek stanowią tu operatory krzyżowania,
które, jako że działają na dwóch losowych chromosomach, realizowane są w obrębie klasy
\texttt{Population}.}


\bigskip

\chapter[Analiza wyników]{\selectlanguage{polish} Analiza wyników}

\bigskip

{\selectlanguage{polish}
Do szerszej analizy działania aplikacji użyłem po dwa zestawy danych uczących dla odnajdywania funkcji oraz
klasyfikacji. Przedstawione zostaną zależności pomiędzy parametrami algorytmu a jego skutecznością.
Postaram się także skonfrontować otrzymane wyniki z tymi opisanymi przez Ferreirę.}


\bigskip

\section[Szukanie funkcji I]{\selectlanguage{polish} Szukanie funkcji I}

\bigskip

{\selectlanguage{polish}
W eksperymencie zamiarem moim było odtworzenie doświadczenia Ferreiry przedstawionego w \cite{Ferreira.anaafsp} w rozdziale 6.1.
Szukaną funkcją jest szybko rosnąca funkcja wielomianowa}

$
y=a^{4}+a^{3}+a^{2}+a
$

\bigskip

{\selectlanguage{polish}
Podobnie jak w rozdziale 3., użyte zostały zbiory \textit{F=\{+,-,*,/,Q\}}, \textit{T=\{a\}, }jednak tym razem
zastosowany został wzór (2) funkcji \textit{fitness}, który, obliczając błąd względnie, jest
mniej czuły na duże amplitudy wartości zwracanych przez programy-osobniki. Algorytm został uruchomiony
stokrotnie dla każdego zestawu parametrów spośród umieszczonych w tabeli 4. Za każdym razem algorytm
wykonywał 50 iteracji dla populacji liczących 30 osobników. Tabela 5. przedstawia parametry modyfikacji
użyte przez algorytm (wartość 0 w nawiasach oznacza modyfikacje, którym nie mogły zostać poddane populacje
składające się z chromosomów jednogenowych),}

{\selectlanguage{polish}
Jako miarę sukcesu przyjąłem stosunek}

{\selectlanguage{polish}
\  $\frac{\sum _{i=0}^{R}b_{i}}{R\cdot f_{\mathit{max}}}\cdot 100\text{\%}$\ \ \ \ \ \ \ \ \ \ \ \ (5)}

{\selectlanguage{polish}
gdzie b\textsubscript{i} oznacza przystosowanie najlepszego osobnika w i-tym (spośród $R$) przebiegu algorytmu,
f\textsubscript{max} zaś maksymalną możliwą do osiągnięcia wartość przystosowania (dla M=100 i
liczby danych treningowych C\textsubscript{t}=10, f\textsubscript{max}=1000). Przedstawiony poniżej wykres 5.
pokazuje zależności pomiędzy długością genu, a procentową miarą sukcesu. }



\begin{center}
\begin{minipage}{11.19cm}
{\itshape
Wykres \stepcounter{Wykres}{\theWykres}: Zależność miary sukcesu od długości chromosomu}
\includegraphics[width=11.19cm,height=6.294cm]{"wykres5.jpg"}
\end{minipage}
\end{center}

\begin{center}
\begin{minipage}{11.245cm}
{\itshape
Wykres \stepcounter{Wykres}{\theWykres}: Zależność liczby odnalezionych prawidłowych rozwiązań od
długości chromosomu}
% [Warning: Image ignored] % Unhandled or unsupported graphics:
\includegraphics[width=11.719cm,height=6.592cm]{"wykres6.jpg"}
\end{minipage}
\end{center}



\begin{center}
\begin{table}
\caption{}
\tablefirsthead{}
\tablehead{}
\tabletail{}
\tablelasttail{}
\begin{supertabular}{|m{4.1130004cm}|m{3.134cm}|m{3.345cm}|}
\hline
{\selectlanguage{polish}\itshape Liczba genów} &
{\selectlanguage{polish}\itshape h} &
{\selectlanguage{polish}\itshape długość genu }\\\hline
{\selectlanguage{polish} 1} &
{\selectlanguage{polish} 4} &
{\selectlanguage{polish} 9}\\\hline
{\selectlanguage{polish} 1} &
{\selectlanguage{polish} 6} &
{\selectlanguage{polish} 13}\\\hline
{\selectlanguage{polish} 1} &
{\selectlanguage{polish} 10} &
{\selectlanguage{polish} 21}\\\hline
{\selectlanguage{polish} 1} &
{\selectlanguage{polish} 12} &
{\selectlanguage{polish} 25}\\\hline
{\selectlanguage{polish} 2} &
{\selectlanguage{polish} 4} &
{\selectlanguage{polish} 18}\\\hline
{\selectlanguage{polish} 2} &
{\selectlanguage{polish} 6} &
{\selectlanguage{polish} 26}\\\hline
{\selectlanguage{polish} 2} &
{\selectlanguage{polish} 10} &
{\selectlanguage{polish} 42}\\\hline
{\selectlanguage{polish} 2} &
{\selectlanguage{polish} 12} &
{\selectlanguage{polish} 50}\\\hline
{\selectlanguage{polish} 3} &
{\selectlanguage{polish} 4} &
{\selectlanguage{polish} 27}\\\hline
{\selectlanguage{polish} 3} &
{\selectlanguage{polish} 6} &
{\selectlanguage{polish} 39}\\\hline
{\selectlanguage{polish} 3} &
{\selectlanguage{polish} 10} &
{\selectlanguage{polish} 63}\\\hline
{\selectlanguage{polish} 3} &
{\selectlanguage{polish} 12} &
{\selectlanguage{polish} 75}\\\hline
{\selectlanguage{polish} 4} &
{\selectlanguage{polish} 4} &
{\selectlanguage{polish} 36}\\\hline
{\selectlanguage{polish} 4} &
{\selectlanguage{polish} 6} &
{\selectlanguage{polish} 52}\\\hline
{\selectlanguage{polish} 4} &
{\selectlanguage{polish} 10} &
{\selectlanguage{polish} 84}\\\hline
{\selectlanguage{polish} 4} &
{\selectlanguage{polish} 12} &
{\selectlanguage{polish} 100}\\\hline
\end{supertabular}
\end{table}
\end{center}



\begin{center}
\begin{table}
\caption{Tabela \stepcounter{Tabela}: Parametry modyfikacji dla rozpatrywanego problemu}
\tablefirsthead{}
\tablehead{}
\tabletail{}
\tablelasttail{}
\begin{supertabular}{|m{4.51cm}|m{4.4300003cm}|}
\hline
{\selectlanguage{polish} mutacja} &
{\selectlanguage{polish} 0.3}\\\hline
{\selectlanguage{polish} IST} &
{\selectlanguage{polish} 0.1 (0)}\\\hline
{\selectlanguage{polish} RIST} &
{\selectlanguage{polish} 0.1 (0)}\\\hline
{\selectlanguage{polish} GT} &
{\selectlanguage{polish} 0.1 (0)}\\\hline
{\selectlanguage{polish} 1PR} &
{\selectlanguage{polish} 0.1 }\\\hline
{\selectlanguage{polish} 2PR} &
{\selectlanguage{polish} 0.4 }\\\hline
{\selectlanguage{polish} GR} &
{\selectlanguage{polish} 0.3 (0)}\\\hline
\end{supertabular}
\end{table}
\end{center}

\bigskip

{\selectlanguage{polish}
Co ciekawe, mimo iż wykres 5. wskazuje na dużą zbieżność jakości rozwiązań znalezionych przez
chromosomy o dużej długości, wykres 6., przedstawiający liczbę znalezionych rozwiązań
prawidłowych (tzn. o wartości \textit{fitness }równej f\textsubscript{max}=1000) w zależności o długości
chromosomu wykazuje, że najlepsze rezultaty osiągają chromosomy o długości 36 i 39. Wynik ten podobny
jest do uzyskanego przez autorkę systemu, opublikowanego w \cite{Ferreira.anaafsp}, a przedstawionego na wykresie 7. Autorka nie
określa w publikacji, co rozumie poprzez \textit{{\quotedblbase}success rate}{}'', \ jednak maksima funkcji
przedstawionej na wykresie 7. wskazują, że wyniki przez nią uzyskane nie różnią się znacząco
od moich. Różnice wynikać mogą z innych parametrów występowania modyfikatorów użytych przeze mnie
oraz z różnic w operacjach mutacji i transpozycji zaznaczonych w rozdziale drugim. }

{\selectlanguage{polish}
Z analizy wykresów 5. i 6. można wywnioskować jeszcze jedną wartą odnotowania właściwość. Choć
przy długich chromosomach średnia wartość przystosowania zachowuje wysoki poziom, wykazując nawet
niewielką tendencję do wzrostu, liczba znalezionych poprawnych rozwiązań spada. Oznacza to, że rzadziej
występujące osobniki o maksymalnych wartościach dostosowania mimo wszystko średnią zawyżają.
Wniosek, że wraz ze wzrostem długości chromosomu zbieżność algorytmu zwiększa się (tzn. maleje
różnorodności osobników) w pó\'zniejszych generacjach, zdają się potwierdzać obserwacje generacji.
Jest to zjawisko niepożądane, gdyż hamuje, czy wręcz zatrzymuje, proces ewolucji\footnote{Wierzchoń w \cite{Wierzchon}
przedstawia metody tzw. koewolucji, wspomagające ewolucję regulując jej przebieg poprzez techniki
adaptacyjne, jednak w omawianym algorytmie nie mają one zastosowania.}.}


\begin{center}
\begin{minipage}{7.408cm}
{\itshape
 % [Warning: Image ignored] % Unhandled or unsupported graphics:
\includegraphics[width=7.408cm,height=9.049cm]{"praca-img023.jpg"}
 Wykres \stepcounter{Wykres}{\theWykres}: Stosunek jakości wyników do długości chromosomów wg Ferreiry}
\end{minipage}
\end{center}
\section[Szukanie funkcji II]{\selectlanguage{polish} Szukanie funkcji II}
{\selectlanguage{polish}
\ Jako drugi przykład zastosowania GEP dla omawianego problemu wybrana została funkcja  $y=4.25a^{2}+\ln
(a^{2})+7.243e^{a}$ wykorzystywana przez Ferreirę w \cite{Ferreira.anaafsp}, jednak w innym kontekście. Zbiór funkcji to \textit{F=\{+,-,/,*,E,L,,C,S,T\}}, gdzie \textit{E }oznacza funkcję
eksponencjalną, \textit{L }jest logarytmem naturalnym, \textit{\ T }oznacza logarytm przy podstawie równej 10,
\textit{S -- }sinus, \textit{C --} cosinus. Zestaw danych treningowych, składający się, jak wyżej, z par
\textit{argument-wartość }funkcji, przedstawiony jest poniżej:}

{\selectlanguage{polish}\sffamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ \texttt{a\ \ f(a)}}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ {}-0.2639725157548009\ \ 3.194980662652764}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ 0.0578905532656938\ \ 1.990520017259985}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ 0.3340252901096346\ \ 8.396637039972868}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ {}-0.2363345775644623\ \ 3.070889769728257}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ {}-0.8557443825668047\ \ 5.879467636957033}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ {}-0.0194437136332785\ \ {}-0.7753263223284588}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ {}-0.1921343881833043\ \ 2.834702257744086}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ 0.5293079101246271\ \ 12.21547266421373}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ {}-0.007889741187284598\ \ {}-2.498039834186359}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ 0.4389698049506311\ \ 10.40717348588088}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ {}-0.1075592926980396\ \ 2.094136356459081}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ {}-0.2745569943771633\ \ 3.239272780108398}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ {}-0.05953332196045281\ \ 1.197012847673475}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ 0.3844929939583523\ \ 9.355807691898551}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ {}-0.8749230207363339\ \ 6.006424530013026}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ {}-0.236546636250546\ \ 3.071897290438372}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ {}-0.1678759417045577\ \ 2.674400531309863}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ 0.9506821818220914\ \ 22.48196398441491}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ 0.9469791595773622\ \ 22.37501611873555}

{\selectlanguage{polish}\ttfamily\color[rgb]{0.13333334,0.13333334,0.13333334}
\ \ 0.6393399100595915\ \ 14.5701285332337}


\bigskip


\bigskip

{\selectlanguage{polish}
W tym przypadku, przy przyjętych parametrach algorytmu, dokładne rozwiązanie nie zostało znalezione.
Algorytm uruchomiony został stukrotnie, za każdym razem wykonując 50 iteracji przy dziesięcioosobnikowej
populacji. Najlepszy osobnik wygenerowany został w 49. przebiegu i 43. iteracji:}


\bigskip

{\selectlanguage{polish}\ttfamily
E+\foreignlanguage{english}{SaEaaaaaa}{\textbar}E+S+aaaaaaa{\textbar}Eaa*aaaaaaa{\textbar}}

$e^{\sin{e^{a}}+a} + e^{\sin{a}+2a} + e^{a}$

{\selectlanguage{polish}
Porównanie tego rozwiązania do funkcji szukanej, prezentuje Wykres 8. (kolor niebieski). Mimo iż wizualnie
wykresy różnią się od siebie w stopniu dość znacznym, różnice bezwzględne między
wartościami obu funkcji są niewielkie. Stąd rozwiązania znalezione w kolejnych przebiegach różnią
się od siebie w o wiele mniejszym stopniu, niż w przykładzie powyżej. Najniższa uzyskana wartość
wyniosła 1914, podczas gdy najwyższa 1963.98 (przy maksimum wynoszącym 2000). Ciekawie wygląda z kolei
rezultat uzyskany przy zastosowaniu takich samych parametrów, ale funkcję przystosowania wyliczając wzorem
(.2), wyrażane przez chromosom:}


\bigskip

{\selectlanguage{polish}
\ \ \ \ \texttt{T*Saaaaaaaa{\textbar}EE*Saaaaaaa{\textbar}-*SEEaaaaaa{\textbar}}}

$\log_{10} {a\sin{a}} + e^{e^{a\sin{a}}} + {e^{a}}^2-\sin{a}$

{\selectlanguage{polish}
Na wykresie 8. funkcja ta została oznaczona kolorem zielonym. Wartość \textit{fitness} wyniosła 1209,91 (po
przeliczeniu z użyciem wzoru (.1) wartość fitness wynosi 1942,834). Jak można zauważyć, różnice w
wartościach funkcji odnalezionej i docelowej najmniejsze są w środkowej części wykresu oraz w
lewostronnym sąsiedztwie x=0. }



\begin{center}
\begin{minipage}{13.229cm}
{\itshape
Wykres \stepcounter{Wykres}{\theWykres}: Kolorem niebieskim oznaczono funkcję znalezioną przy błędzie
bezwzględnym, zielonym - przy błędzie relatywnym. Kolorem czerwonym oznaczona funkcja docelowa. }
\includegraphics[width=13.229cm,height=13.229cm]{"praca-img024.png"}\end{minipage}
\end{center}

\bigskip

{\selectlanguage{polish}
Różnicę między tendencjami wzrostu jakości wraz kolejnymi populacjami ilustruje wykres 9. Widać na nim,
że w obu przypadkach najczęściej rozwiązania znajdowane były w końcowych generacjach.}

{\selectlanguage{polish}
 }

\begin{center}
\begin{minipage}{17cm}
{\itshape
Wykres \stepcounter{Wykres}{\theWykres}. }
\includegraphics[width=17cm,height=6.048cm]{praca-img025.jpg}\end{minipage}
\end{center}

\bigskip

\section[Klasyfikacja I]{\selectlanguage{polish} Klasyfikacja I}

\bigskip

{\selectlanguage{polish}
W teście tym porównane zostaną wyniki klasyfikacji osiągnięte metodami zaprezentowanymi w rozdziale 3.2.
Rozpatrywany problem, diagnostyka raka piersi\footnote{Frank, A. \& Asuncion, A. (2010). UCI Machine Learning
Repository. Irvine, CA: University of California, School of Information and Computer Science}, dostarcza zestaw 699
danych treningowych, składających się z dziewięciu parametrów o wartościach 1-10,
reprezentujących skatalogowane cechy badanej próbki, oraz dwie klasy: \ nowotwór złośliwy, oznaczony jako
4, bąd\'z łagodny, oznaczony jako 2 (parametr będący identyfikatorem próbki pominięto). Jak
zostało tam opisane, technika wykorzystująca {\quotedblbase}czysty'' GEP poradziła sobie z tym zadaniem w
sposób co najmniej zadowalający (ponad 97\% poprawnie zaklasyfikowanych próbek). Dla porównania,
zaimplementowana przez mnie wersja algorytmu, została uruchomiona dziesięć razy przy trzydziestu generacjach
złożonych z dziesięciu osobników. Za dane uczące posłużył pierwsze 499 zestawów, pozostałe
200 zostały potraktowane jako dane testowe. }

{\selectlanguage{polish}
średnia wartość najlepszych rezultatów uzyskanych każdorazowo wyniosła 0,7286952. Najlepszy z
wygenerowanych zestawów reguł wyewoluował w 19. generacji siódmego przebiegu algorytmu. Poniżej
przedstawione zostały zbiory oraz parametry użyte do eksperymentu, oraz osiągnięty genotyp i fenotyp
(operator X oznacza XOR, czyli alternatywa wykluczająca) z przypisanymi już wartościami parametrów}


\begin{center}
\begin{table}
\tablefirsthead{}
\tablehead{}
\tabletail{}
\tablelasttail{}
\begin{supertabular}{|m{4.5360003cm}|m{4.3770003cm}|}
\hline
{\selectlanguage{polish} T } &
{\selectlanguage{polish} \{a,b,c,d,e,f,g,h,i\}}\\\hline
{\selectlanguage{polish} F} &
{\selectlanguage{polish} \{I,N,A,O,X\}}\\\hline
{\selectlanguage{polish} liczba genów w chromosomach} &
{\selectlanguage{polish} 2}\\\hline
{\selectlanguage{polish}\itshape h} &
{\selectlanguage{polish} 5}\\\hline
{\selectlanguage{polish} mutacja} &
{\selectlanguage{polish} 0.3}\\\hline
{\selectlanguage{polish} IST} &
{\selectlanguage{polish} 0.2}\\\hline
{\selectlanguage{polish} RIST} &
{\selectlanguage{polish} 0.2}\\\hline
{\selectlanguage{polish} GT} &
{\selectlanguage{polish} 0.2}\\\hline
{\selectlanguage{polish} 1PR} &
{\selectlanguage{polish} 0.1}\\\hline
{\selectlanguage{polish} 2PR} &
{\selectlanguage{polish} 0.3}\\\hline
{\selectlanguage{polish} GR} &
{\selectlanguage{polish} 0.4}\\\hline
\end{supertabular}
\end{table}
\end{center}

\bigskip

{\selectlanguage{polish}\ttfamily
Nf{\textgreater}2IAh!7h{\textgreater}4d{\textless}8e{\textgreater}3h{\textgreater}3c{\textless}7f{\textless}8h{\textless}1f=5a=8g{\textgreater}1h!2{\textbar}OOIIAh!7b{\textgreater}1b=4b{\textless}7a{\textgreater}2f{\textless}10f!0a=0d=8b=5c{\textgreater}8}


\bigskip

JEŚLI 

{\selectlanguage{polish}\ttfamily  \~{} (f {\textgreater} 2)

 TO\ \ klasa 1}


\bigskip
JEŚLI  

{\selectlanguage{polish}\ttfamily  ((JEŚLI b<7 TO a<2 W PRZECIWNYM RAZIE f<10)\ LUB\ (f$\neq$0  I  a=0)\ LUB \ (JEŚLI h$\neq$7 TO b>1 W PRZECIWNYM RAZIE b=4))

TO\ \ klasa 2}


\bigskip

{\selectlanguage{polish}
Pierwszy warunek, dotyczący raka łagodnego, wydaje się być zdumiewająco prosty, zważywszy na zakres
danych oraz złożoność problemu, jednak przyglądając się danym wejściowym zauważyć można,
że faktycznie wartość tego jednego parametru może z dużym prawdopodobieństwem sukcesu zdecydować o
diagnozie.}

{\selectlanguage{polish}
\ \ Wartość funkcji przystosowania wyniosła 0,844254, co można uznać za wynik dobry. Program sprawdzony na
danych testowych uzyskał rezultat co najmniej zadowalający, jednak nie tak dobry, jak wskazywałaby na to
wartość \textit{fitness.}}

{\selectlanguage{polish}
Eksperyment został powtórzony w podobny sposób, jednak tym razem każdorazowo algorytm iterowany był
\foreignlanguage{english}{stukrotnie, wielko}ść populacji również wynosiła 100. Wartość fitness
najlepszego rozwiązania nie różni się wiele co do wartości bezwzględnej od poprzedniego, wynosząc
0,868225, jednak skuteczność {\quotedblbase}testowa'' uzyskanego fenotypu wyniosła 95,5\% (przy Se=0,945,
Sp=0,965). }

{\selectlanguage{polish}
średnia wartość najlepszych rozwiązań wyniosła tu 0,78619603, zaś, \foreignlanguage{english}{podobnie
jak} w przykładach dotyczących szukanych funkcji, im pó\'zniejsza populacja, tym większe skupienie
rozwiązań najlepszych (wykres . Można z tego wnioskować, że przy tak dobranych parametrach (w tym liczbie
osobników w populacji oraz liczby iteracji etc.) zmiany ewolucyjne zachodzą, dając pożądane rezultaty,
mimo iż pozornie populacja staje się coraz mniej zróżnicowana.}


\bigskip



\begin{center}
\begin{minipage}{16cm}
{\itshape
Wykres \stepcounter{Wykres}{\theWykres}: Liczba rozwiązań w zależności od numeru generacji}

\includegraphics[width=16cm,height=8.999cm]{"wykres10.jpg"}
\end{minipage}
\end{center}
\clearpage\section{Klasyfikacja II}

\bigskip

\ Przedmiotem tego badania są dane uczące z zakresu składania tekstu, celem zaś wykazanie zależności
pomiędzy liczbą populacji a efektywnością algorytmu. 

\ Za dane treningowe posłużył zestaw około tysiąca przykładów opisanych dziesięcioma parametrami
takimi jak wymiary bloku czy stosunek pikseli białych do czarnych. Podzielone zostały one na pięć klas,
oznaczonych numerami 1-5, oznaczających odpowiednio: tekst, linię poziomą, obraz, linię pionową
oraz grafikę. Zadaniem algorytmu jest więc wyznaczenie reguły określającej jakim elementem strony jest
dany blok.\footnote{Frank, A. \& Asuncion, A. (2010). UCI Machine Learning
Repository. Irvine, CA: University of California, School of Information and Computer Science}

\ Aplikacja została uruchomiona ośmiokrotnie, algorytm każdorazowo iterowany 30 razy, z parametrami
prawdopodobieństwa wystąpienia operacji genetycznych takimi, jak w poprzednim eksperymencie. Zgodnie z
przyjętym wariantem algorytmu, każdy chromosom składał się z pięciu genów. Wielkość populacji
była zwiększana co drugie uruchomienie programu. Co ciekawe, otrzymane wyniki, zarówno te najlepsze, jak i
średnia wartość \textit{fitness} wszystkich osobników, nie różniły się pomiędzy sobą w
sposób znaczący. Przedstawione zostało to w tabeli poniżej.

\begin{center}
\tablefirsthead{}
\tablehead{}
\tabletail{}
\tablelasttail{}
\begin{supertabular}{|m{1.497cm}|m{5.5820003cm}|m{5.467cm}|m{3.656cm}|}
\hline
 Lp. &
 Wielkość populacji &
 Najlepszy wynik &
 średnio\\\hline
1 &
10 &
0.801775 &
0.511627\\\hline
2 &
10 &
 0.767621 &
 0.452215\\\hline
2 &
20 &
0.769436 &
 0.534798\\\hline
3 &
20 &
0.822262 &
h 0.524992\\\hline
4 &
30 &
0.816203 &
h 0.536234\\\hline
5 &
30 &
0.855515 &
h 0.537924\\\hline
6 &
50 &
0.846025 &
h 0.516721\\\hline
7 &
50 &
0.823092 &
h 0.496623\\\hline
\end{supertabular}
\end{center}

\bigskip

Można by w związku z tym przypuścić, że wielkość populacji nie wpływa znacząco na jakość
uzyskanych wyników. Jednak, co widać na wykresie 11., okazuje się, iż wraz ze wzrostem liczby osobników w
generacji rośnie z jednej strony ich jakość, z drugiej zaś prędkość jej wzrostu w pierwszych iteracjach
algorytmu. Biorąc pod uwagę, że ewolucja hamuje w podobnym momencie (mając jednocześnie na uwadze
czynnik losowy), można wywnioskować, że zwiększając liczebność populacji można
{\quotedblbase}zaoszczędzić'' na liczbie iteracji.



\begin{center}
\begin{minipage}{17.014cm}
{\itshape
Wykres \stepcounter{Wykres}{\theWykres}: Rezultaty uzyskane w zależności od wielkości populacji}
% [Warning: Image ignored] % Unhandled or unsupported graphics:
\includegraphics[width=17.014cm,height=8.147cm]{"wykres11.jpg"}
\end{minipage}
\end{center}

\bigskip


\bigskip

\clearpage\chapter{Podsumowanie}

\bigskip

Celem niniejszej pracy było pokazania przykładów zastosowania algorytmu Gene Expression Programing oraz zalet
takiego podejścia. Algorytm w sposób nowatorski rozwija koncepcję programowania genetycznego odwołując
się do zjawisk zachodzących w naturze. Inspirując się mechanizmami biologicznymi, Autorce udało
się stworzyć projekt o szerokiej gamie zastosowań. Ze względu na używany przezeń model reprezentacji
danych, algorytm ten jest narzędziem wysoce uniwersalnym, a faktyczna liczba możliwości jego wykorzystania w
rozwiązywaniu zagadnień poszukiwania reguł jest trudna do oszacowania. Dotyczy to nie tylko oryginalnego
wariantu, zaproponowanego przez Candidę Ferreirę, który sam w sobie jest potencjalnie potężnym
narzędziem. Może on stanowić bazę dla konstruowania systemów wysoce wyspecjalizowanych,
wykorzystujących zmodyfikowane do indywidualnych potrzeb wersje alternatywne, co, mam nadzieję, udało mi
się przedstawić.

Oprócz rzeczonej uniwersalności, wartość GEP niewątpliwie podnosi jego wysoka skuteczność. Z całą
pewnością da się również zauważyć wady algorytmu. Tą, którą osobiście odczułem
najbardziej, jest dosyć wysoka złożoność obliczeniowa, szacowana przez ${O(n \cdot f)}$ gdzie ${n}$jest 
wielkością populacji, zaś ${f}$jest liczbą danych uczących (dotyczy podstawowej wersji).
Może to utrudnić zastosowanie algorytmu w systemach o wymaganym krótkim czasie uzyskania odpowiedzi (rozwiązania). W zależności od implementacji,
przeszkodą może (choć nie musi) być konieczność zdefiniowania działania operatorów funkcyjnych, np.
unikalnych dla danej sytuacji. 

W rozwiązaniu ostatniego, potencjalnego, mankamentu, oraz przy konstrukcji wielozadaniowej platformy
sięgnąć należałoby do metod programowania obiektowego z wykorzystaniem konstrukcyjnych wzorców
projektowych. Ułatwia to m.in. rozwijanie aplikacji pod kątem wykorzystania GEP do problemów innej natury czy
też modyfikacji mechanizmów algorytmu.

Z kolei, jeśli chodzi o zwiększenie wydajności obliczeniowej czy pamięciowej, z pomocą mogłyby
przyjść techniki obliczeń równoległych czy rozproszonych.

\bibliography{"bibliografia"}
\end{document}
